Shortest Path – GATE CSE AlgorithmsPractice Questions & PYQs

D^(k)[i][j] represents the weight of a shortest path from vertex i to vertex j for which all intermediate vertices are in the set {1, 2, ..., k}. When k = 0, D^(0)[i][j] is the direct edge weight (or infinity if no direct edge). When k = n, D^(n)[i][j] gives the true shortest path between every pair, using any subset of vertices as intermediates.

During k=1, we check if path through vertex 1 improves D[i][j] for all i,j. D[4][2]: current = ∞. Via vertex 1: D[4][1] + D[1][2] = 2 + 3 = 5. Since 5 < ∞, update D[4][2] = 5. The path is 4→1→2 with total weight 5.

A: Floyd-Warshall with boolean OR/AND computes transitive closure in O(n³). B: Floyd-Warshall correctly handles negative edges (unlike Dijkstra) as long as no negative cycles exist. D: After Floyd-Warshall, the diameter = max over all pairs (i,j) of D[i][j] - simply a scan of the final matrix. C: Minimum Spanning Tree is solved by Prim's or Kruskal's algorithms. Floyd-Warshall gives shortest paths, not minimum spanning trees - these are fundamentally different problems.