Weighted Graphs: Shortest Paths and Spanning Trees

Which condition must the edge weights satisfy for Dijkstra's algorithm to be guaranteed correct?

Run Dijkstra's algorithm on graph H from source 0. Ties never occur here.

// directed weighted graph H, 6 vertices; u: (v, weight) ...
0: (3, 2)  (4, 7)
1: (2, 6)  (5, 2)
2:
3: (1, 8)  (4, 3)  (5, 10)
4: (1, 1)  (2, 12)
5: (2, 3)

In which order are the vertices settled (removed from the priority queue as final)?

Run Dijkstra on graph H from 0 again.

// directed weighted graph H, 6 vertices; u: (v, weight) ...
0: (3, 2)  (4, 7)
1: (2, 6)  (5, 2)
2:
3: (1, 8)  (4, 3)  (5, 10)
4: (1, 1)  (2, 12)
5: (2, 3)

What is the array dist[0..5] right after the third vertex has been settled and its edges relaxed?

In graph H, what is the shortest distance from 0 to 2, and which path achieves it?

// directed weighted graph H, 6 vertices; u: (v, weight) ...
0: (3, 2)  (4, 7)
1: (2, 6)  (5, 2)
2:
3: (1, 8)  (4, 3)  (5, 10)
4: (1, 1)  (2, 12)
5: (2, 3)

Dijkstra from source 1 produced this predecessor array (−1 means none):

index:  0   1   2   3   4   5
pred:   2  -1   1   1   3   4

Which shortest path to vertex 5 does it describe?

A directed graph has the edges 0 → 1 (weight 2), 0 → 2 (weight 5) and 2 → 1 (weight −4). A textbook Dijkstra, which never updates a vertex once it is settled, runs from 0. What does it report for dist[1], and what is the true shortest distance?

What is the running time of Dijkstra's algorithm with a binary-heap priority queue, on adjacency lists?

You must run Dijkstra on a complete graph (every pair of vertices joined, so E ≈ V²). Which implementation is asymptotically faster?

In the lazy-deletion Dijkstra below, what is the purpose of the marked line?

long[] top = pq.poll();
int u = (int) top[1];
if (top[0] > dist[u]) continue;     // <-- this line
for (int[] e : adj.get(u)) { /* relax */ }

What does this print?

PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
pq.add(new int[]{3, 9});
pq.add(new int[]{1, 4});
pq.add(new int[]{2, 4});
pq.add(new int[]{0, 7});
System.out.print(pq.poll()[1] + " ");
System.out.print(pq.poll()[1] + " ");
System.out.println(pq.size());

Does this compile under Java 8 (with import java.util.*;)?

PriorityQueue<int[]> pq =
    new PriorityQueue<>(Comparator.comparingInt(a -> a[1]).reversed());

Bellman–Ford runs from source 0 on a directed graph with 4 vertices. In every round it relaxes the edges in this order:

2 -> 3 (1),   1 -> 2 (-2),   0 -> 1 (4),   0 -> 2 (5)

What is dist[0..3] after round 2?

Bellman–Ford has finished its V − 1 rounds on a graph with V vertices. You run one more round and some dist value still decreases. What does this mean?

A connected undirected graph has 12 vertices and 30 edges. How many edges does each of its spanning trees contain?

Which statement is the cut property used to prove Prim's and Kruskal's algorithms correct?

Run Kruskal's algorithm on graph W (edges sorted by weight; equal weights by smaller first endpoint).

// undirected weighted graph W, vertices 0..6; edge: weight
0-1: 4   0-2: 3   1-2: 5   1-3: 2   2-3: 7   2-4: 8
3-4: 6   3-5: 9   4-5: 1   4-6: 5   5-6: 4

Which edge is the last one added to the tree?

What is the total weight of a minimum spanning tree of graph W?

// undirected weighted graph W, vertices 0..6; edge: weight
0-1: 4   0-2: 3   1-2: 5   1-3: 2   2-3: 7   2-4: 8
3-4: 6   3-5: 9   4-5: 1   4-6: 5   5-6: 4

Run Prim's algorithm on graph W starting at vertex 0 (among equal-weight candidates, take the smaller vertex). In what order are the vertices added to the tree?

// undirected weighted graph W, vertices 0..6; edge: weight
0-1: 4   0-2: 3   1-2: 5   1-3: 2   2-3: 7   2-4: 8
3-4: 6   3-5: 9   4-5: 1   4-6: 5   5-6: 4

A union–find on elements 0–7 starts with parent[i] = i and size[i] = 1. find uses full path compression. union(a, b) computes ra = find(a), rb = find(b); if they differ, the root of the smaller set is attached under the other root, and on equal sizes rb goes under ra.

union(0, 1); union(2, 3); union(0, 2); union(4, 5);
union(6, 7); union(5, 7); union(3, 7); find(7);

What is the parent array at the end?

Elements 0–9 start in separate sets. After these operations, how many disjoint sets are there?

union(1, 2); union(3, 4); union(2, 4); union(5, 6);
union(1, 3); union(7, 7); union(8, 9); union(9, 5);

A naive union–find has no union by size and no path compression: union(a, b) sets parent[find(a)] = find(b). Starting from 5 singletons 0–4, you call union(0, 1); union(0, 2); union(0, 3); union(0, 4);. How many parent links does find(0) now follow to reach the root?

With both union by rank (or size) and path compression, what is the amortized cost of a union–find operation on n elements?

Compare, on graph W, the MST with the shortest-path tree (SPT) that Dijkstra builds from vertex 0.

// undirected weighted graph W, vertices 0..6; edge: weight
0-1: 4   0-2: 3   1-2: 5   1-3: 2   2-3: 7   2-4: 8
3-4: 6   3-5: 9   4-5: 1   4-6: 5   5-6: 4

Which edge is in the shortest-path tree but not in the MST?

You add the same constant c > 0 to the weight of every edge of a connected weighted graph. Which statement is true?

What is the running time of Kruskal's algorithm with union by size and path compression, and which step dominates?

Explain, with a concrete graph of at most four vertices, why Dijkstra's algorithm can give a wrong distance when an edge has a negative weight. Which algorithm would you use instead, and at what cost?

State the cut property of minimum spanning trees, and use it to explain why each edge that Kruskal's algorithm accepts belongs to an MST.

A student claims: "The minimum spanning tree contains the shortest path from any vertex to any other, so Dijkstra is unnecessary once you have an MST." Refute the claim with a small example and explain what each tree minimises.

Explain the two optimisations of union–find — union by size (or rank) and path compression. For each, say what problem it prevents, and state the combined amortized cost.

Write a static method boolean hasCycle(int n, int[][] edges) that decides whether the undirected graph with vertices 0 … n − 1 and the given edges contains a cycle, using a union–find structure (union by size and path compression) instead of DFS. Treat a self-loop or a repeated edge as a cycle.

Write a static method long primMst(List<List<int[]>> adj) that returns the total weight of a minimum spanning tree of a connected undirected weighted graph (each adj.get(u) holds {v, w} pairs, both directions stored), using Prim's algorithm with a PriorityQueue. If the graph is not connected, return −1.