Shortest Path – GATE CSE AlgorithmsPractice Questions & PYQs

The predecessor matrix π[i][j] stores the predecessor of j on the shortest path from i to j. To reconstruct path from u to v: start at current = v, then follow current = π[u][current] repeatedly until current = u, collecting vertices in reverse. Then reverse the collected sequence to get the path u → ... → v. This traces backward from the destination using the fixed source u as the first index.

Counting finite entries in the matrix where i ≠ j: (1,2)=5 ✓, (1,3)=9 ✓, (1,4)=10 ✓, (2,3)=4 ✓, (2,4)=5 ✓, (3,4)=1 ✓, (2,1)=∞ ✗, (3,1)=∞ ✗, (3,2)=∞ ✗, (4,1)=∞ ✗, (4,2)=∞ ✗, (4,3)=∞ ✗. Total finite pairs = 6. This corresponds to a DAG where vertices are ordered 1→2→3→4 with no backward edges.

A: The shortest path tree encodes one shortest path from s to every reachable vertex. B: It uses only edges from the original graph. D: A tree on V reachable vertices has exactly V-1 edges. C is FALSE - the shortest path tree minimizes individual path lengths from the source, not the total weight sum (that's the MST's property, and even MST minimizes total weight, not Dijkstra's tree).

A and C both refer to the maximum bottleneck (widest path) problem: find a path where the minimum edge weight is maximized. Dijkstra's greedy structure can be adapted by replacing the relaxation condition: instead of d[v] = min(d[v], d[u]+w), use d[v] = max(d[v], min(d[u], w)). B requires Bellman-Ford for negative edges. D uses topological-sort-based DP for DAGs with negatives - not Dijkstra's.

The initialization for Floyd-Warshall represents paths using no intermediate vertices (k=0). D^(0)[i][i] = 0 because the path from any vertex to itself using no intermediate vertices has weight 0. D^(0)[i][j] = w(i,j) if a direct edge exists (the only path without intermediates is the direct edge). D^(0)[i][j] = ∞ if no direct edge exists and i ≠ j, since no path is known yet.

Running Dijkstra from 1: d[1]=0, d[2]=2, d[3]=min(6,2+3)=5, d[4]=2+8=10, d[5]=min(5+7,10+2)=12, d[6]=min(10+5,12+1)=13. The shortest path is 1→2→3 wait - recalculating: 1→2→4→5→6 = 2+8+2+1=13. So d[6]=13.

Each vertex is inserted into the priority queue exactly once (at initialization or first discovery) and extracted exactly once when it has the minimum distance among unfinalized vertices. Since the graph is connected and has V vertices, exactly V extract-min operations are performed - one per vertex. This contrasts with decrease-key which may occur up to E times.

A negative weight self-loop (v → v with negative weight) is itself a negative weight cycle. During initialization, D[v][v] = 0 (not the self-loop weight). However, during the iteration where k = v, the update D[v][v] = min(D[v][v], D[v][v] + D[v][v]) may not catch it directly. The self-loop weight w(v,v) < 0 is loaded into D^(0)[v][v] if not overridden by 0. In standard Floyd-Warshall, D[i][i] is initialized to 0 - so the negative self-loop is detected only if it propagates through the path updates and reduces D[v][v] below 0.

Initial: d[s]=0, all others ∞. Extract s: d[a]=1, d[b]=4. Extract a (d=1): d[b]=min(4,1+2)=3, d[t]=1+6=7. Extract b (d=3): d[t]=min(7,3+3)=6. Extract t (d=6). Final: d[s]=0, d[a]=1, d[b]=3, d[t]=6. Shortest path to t is s→a→b→t = 1+2+3 = 6.

The Floyd-Warshall DP has three indices: k (intermediate vertex, ranges 0 to n), i (source vertex, ranges 1 to n), j (destination vertex, ranges 1 to n). Total distinct subproblems = (n+1) × n × n ≈ n³. Each subproblem D^(k)[i][j] is computed in O(1) using previously computed values. Total work = O(n³).

Running Dijkstra from 1: d[1]=0. Extract 1: d[2]=6, d[3]=1, d[4]=5. Extract 3(d=1): d[2]=min(6,3)=3, d[4]=min(5,6)=5, d[5]=7. Extract 2(d=3): d[5]=min(7,5)=5. Extract 4(d=5): d[5]=min(5,6)=5. Extract 5(d=5). Distances: d[2]=3, d[3]=1, d[4]=5, d[5]=5. Sum = 3+1+5+5 = 14. Wait recalculating: 1→3(1), 1→3→2(1+2=3), 1→4(5), 1→3→2→5(1+2+2=5). Sum = 1+3+5+5 = 14.

Floyd-Warshall maintains an n × n distance matrix D where D[i][j] stores the current best known shortest path from i to j. Since the update for iteration k can be done in-place (row k and column k remain unchanged during iteration k), only one n × n matrix is needed at any time. Space complexity = O(n²). If path reconstruction is needed, an additional n × n predecessor matrix π also requires O(n²) space.

Without a priority queue, finding minimum distance vertex takes O(V), done V times → O(V²).

Bellman-Ford runs in O(VE) time due to V-1 iterations of relaxing all edges.

During iteration k of Floyd-Warshall: D[k][j] = min(D[k][j], D[k][k] + D[k][j]). Since D[k][k] = 0 (assuming no negative cycle detected yet), this simplifies to D[k][j] = D[k][j] - no change. Similarly D[i][k] = min(D[i][k], D[i][k] + D[k][k]) = D[i][k] - no change. This is precisely why in-place updates are valid. C: If there is a negative cycle through k, then after the update D[k][k] = min(0, D[k][k]+D[k][k]) could become negative. D is FALSE.

Dijkstra's assumes non-negative weights. Negative edges can cause it to miss shorter paths discovered after a node is finalized.

Initial D^(0): D[1][2]=3, D[2][3]=1, D[1][3]=8, D[1][1]=D[2][2]=D[3][3]=0, all others ∞. After k=1 (intermediate vertex 1): no changes (no paths go through 1 to improve others). After k=2 (intermediate vertex 2): D[1][3] = min(D[1][3], D[1][2] + D[2][3]) = min(8, 3+1) = 4. After k=3: no further improvement. Final D[1][3] = 4.

1. The algorithm extracts the strain with the minimum tentative cost from the priority queue. In the given state, (5, Q) is extracted. Strain Q is now marked as visited, and its shortest path cost is finalized to 5.

2. Next, the algorithm processes all neighbors of Q:

   • Neighbor P: Strain P is already in the visited set ({S, P, Q}). Therefore, it is ignored.
   • Neighbor R: Strain R is not visited. Its current tentative distance is dist[R]=9. The path via Q would be dist[Q] + weight(Q, R) = 5 + 1 = 6. Since 6 < 9, dist[R] is updated to 6. The priority queue is updated to reflect this new, shorter path to R; (6, R) is added, effectively superseding any previous entry for R (like (9, R)).
   • Neighbor T: Strain T is not visited. Its current tentative distance is dist[T]=infinity. The path via Q would be dist[Q] + weight(Q, T) = 5 + 7 = 12. Since 12 < infinity, dist[T] is updated to 12. (12, T) is added to the priority queue.

3. After processing Q's neighbors, the tentative distances are: dist[S]=0, dist[P]=3, dist[Q]=5, dist[R]=6, dist[T]=12. The priority queue (sorted by cost) now contains {(6, R), (12, T)}.

Comparing this with the options:

• Option A incorrectly keeps dist[R]=9 and (9, R) in the PQ.
• Option B matches the calculated state.
• Option C fails to update dist[T] and add (12, T) to the PQ.
• Option D incorrectly includes the superseded (9, R) entry in the priority queue along with the updated (6, R).

Bellman-Ford works with negative edge weights, whereas Dijkstra fails when negative edges are present. Dijkstra is generally faster for non-negative graphs.

A: Dijkstra's is greedy (always picks the minimum distance unvisited vertex); Bellman-Ford uses DP (relaxes all edges V-1 times). B: Dijkstra's fails with negative weights; Bellman-Ford handles them correctly. C: Dijkstra's with array is O(V²); Bellman-Ford is O(VE). D: It is Bellman-Ford that detects negative cycles (not Dijkstra's), so D is FALSE.