Shortest Path – GATE CSE AlgorithmsPractice Questions & PYQs

Floyd-Warshall uses Dynamic Programming. The key DP insight is: D^(k)[i][j] = shortest path from i to j using only vertices {1, 2, ..., k} as intermediates. Each subproblem builds on smaller subproblems, and subproblems overlap across different (i, j) pairs. The recurrence D^(k)[i][j] = min(D^(k-1)[i][j], D^(k-1)[i][k] + D^(k-1)[k][j]) fills the table bottom-up.

Graph edges: 1→2(1), 2→3(1), 3→4(1), 4→1(1) - a cycle. D^(0)[1][3]=∞. After k=2: D[1][3]=min(∞, D[1][2]+D[2][3])=min(∞,1+1)=2. After k=3: D[1][3]=min(2, D[1][3]+D[3][3])=2 (no change). The shortest path 1→2→3 has weight 1+1=2. Alternative: 1→2→3 directly =2; via cycle: 1→...→4→1→2→3 = 1+1+1+1+1=5 - longer. D[1][3] = 2.

B: Floyd-Warshall handles negative edge weights (without negative cycles), while Dijkstra cannot - making Floyd-Warshall the correct choice. C: For dense graphs (E = Θ(n²)), Floyd-Warshall's O(n³) matches or beats repeated Dijkstra, and its simple triple-loop is easier to implement. A: For sparse non-negative graphs, repeated Dijkstra with a heap (O(n(E + n) log n)) is faster than Floyd-Warshall O(n³). D: BFS from each vertex is O(n(V+E)) - faster than Floyd-Warshall for unweighted graphs.

Dijkstra's fails when any edge has a negative weight. Even a single negative edge can cause incorrect results because the greedy assumption - that a finalized vertex has its true shortest distance - breaks down. A self-loop with positive weight is simply ignored (it can't improve any distance). Zero weights are valid. A complete graph with distinct positive weights works correctly.

Negative weights break greedy correctness.

If further relaxation is possible after V-1 iterations, it indicates a negative cycle.

Time complexities: Fibonacci heap = O(E + V log V) [best], Binary min-heap = O((V + E) log V) [middle], Unsorted array = O(V²) [worst for sparse, best for dense]. For sparse graphs (E = O(V)), Fibonacci heap is fastest. For dense graphs (E = O(V²)), array-based O(V²) beats binary heap O(V² log V). In general asymptotic ordering for sparse graphs: Fibonacci < Binary heap < Array.

Bellman-Ford is used for single source shortest path and detects negative cycles.

Bellman-Ford works by relaxing all edges repeatedly for V-1 iterations because the longest possible shortest path can have at most V-1 edges. It can handle negative weights but not negative cycles.

The in-place update is valid because D^(k)[k][k] = 0 (no negative cycles assumed), so D^(k)[i][k] = min(D^(k-1)[i][k], D^(k-1)[i][k] + D^(k-1)[k][k]) = D^(k-1)[i][k]. Similarly D^(k)[k][j] = D^(k-1)[k][j]. Row k and column k remain unchanged during iteration k, so using the same matrix for read and write produces correct results.

Edge relaxation checks whether the known shortest path to v can be improved by going through u. If d[u] + w(u,v) < d[v], then the path through u is better, so d[v] is updated to d[u] + w(u,v) and π[v] = u. This is the fundamental relaxation step common to both Dijkstra's and Bellman-Ford algorithms.

When all edge weights are equal (or unit weights), BFS finds single-source shortest paths in O(V + E) time, which is better than Dijkstra's O((V + E) log V). BFS naturally explores vertices in non-decreasing order of distance when weights are uniform, making the priority queue unnecessary. Bellman-Ford is O(VE) - slower. Floyd-Warshall is O(V³) - for all-pairs, not single-source.

With a binary heap: each of V extract-min is O(log V), each of E decrease-key is O(log V) → O((V+E) log V).

With a Fibonacci heap, Dijkstra's algorithm achieves O(E + V log V). The V extract-min operations cost O(log V) each amortized (total O(V log V)), and E decrease-key operations cost O(1) amortized each (total O(E)). This is the best known complexity for Dijkstra's algorithm and is optimal for sparse graphs where E = O(V).

The transitive closure variant of Floyd-Warshall uses boolean values (0 or 1) instead of distances and replaces min with OR and addition with AND. The algorithm still uses three nested loops each of size n, giving O(n³) time complexity. Space is O(n²) for the boolean matrix T[n][n]. This is the same asymptotic complexity as the standard Floyd-Warshall but with simpler bitwise operations.

For dense graphs (E = O(n²)): Floyd-Warshall = O(n³). Dijkstra with binary heap from each vertex = O(n × (n + E) log n) = O(n × n² log n) = O(n³ log n) - worse. Dijkstra with array from each vertex = O(n × n²) = O(n³) - same as Floyd-Warshall. So for dense graphs, Floyd-Warshall is at least as good, and simpler to implement. B and C are both correct observations.

Dijkstra assumes non-negative edge weights. Negative weights break correctness.

The current state is: dist = {A:0, B:2, C:5, D:6, E:inf}, visited = {A, B}, PQ = {(5, C), (6, D)}.

1. Extract Node: From the priority queue {(5, C), (6, D)}, the node with the minimum latency is (5, C). So, C is extracted.

2. Mark Visited: Node C is marked as visited. The visited set becomes {A, B, C}.

3. Process Neighbors of C:

   • Neighbor A: A is already in the visited set. It is skipped.
   • Neighbor B: B is already in the visited set. It is skipped.
   • Neighbor D: D is not in the visited set.
     • Calculate the new tentative distance to D via C: new_dist_D = dist[C] + weight(C,D) = 5 + 1 = 6.
     • Compare this new_dist_D (6) with the current tentative distance to D (dist[D] = 6). Since new_dist_D is not strictly less than dist[D], dist[D] is not updated. The entry (6, D) remains in the priority queue with its current priority.

4. Final State: After processing node C, the tentative distances remain dist = {A:0, B:2, C:5, D:6, E:inf}. The priority queue now contains only the remaining unvisited node with an entry, PQ = {(6, D)}. The set of visited nodes is {A, B, C}.

Option A accurately reflects this state. Options B, C, and D contain errors related to distance updates, priority queue management, or node extraction order.

Floyd-Warshall has three nested loops, each running n times: the outer loop over intermediate vertices k (1 to n), and two inner loops over source i and destination j (both 1 to n). Each iteration does O(1) work. Total time = O(n³). This is independent of the number of edges E, making it suitable for dense graphs.

Running Dijkstra from A: d[A]=0, d[B]=1, d[C]=min(4, 1+2)=3, d[D]=min(1+5, 3+1)=4. The shortest path is A→B→C→D with total weight 1+2+1=4.