Shortest Path – GATE CSE AlgorithmsPractice Questions & PYQs

Initial D^(0)[1][1]=0, D[1][2]=2, D[2][1]=-3, D[2][3]=1. After k=1: D[2][2]=min(0, D[2][1]+D[1][2])=min(0,-3+2)=min(0,-1)=-1. D[2][3]=min(1,∞)=1 (no change). After k=2: D[1][1]=min(0, D[1][2]+D[2][1])=min(0,2+(−3))=min(0,−1)=−1. D[1][1] = −1. Since D[1][1] < 0, this indicates a negative weight cycle: 1→2→1 with weight 2+(−3) = −1.

Bellman-Ford runs for V-1 iterations and then performs one more iteration to check for further relaxation. If distances still decrease, it detects a negative cycle. It still terminates but does not produce valid shortest paths.

If any edge can still be relaxed after V-1 iterations, it indicates the presence of a negative weight cycle reachable from the source.

With a binary min-heap: each vertex is extracted once - V extract-min operations each costing O(log V), giving O(V log V). Each edge causes at most one decrease-key operation costing O(log V), giving O(E log V). Total: O(V log V + E log V) = O((V + E) log V). For a connected graph where E ≥ V-1, this simplifies to O(E log V).

Each directed edge (u, v) is relaxed exactly once - when vertex u is extracted from the priority queue and its adjacency list is scanned. Since there are E directed edges (or 2E for undirected), the number of relaxation attempts is E (or 2E for undirected). Only successful relaxations trigger decrease-key; the total relaxation attempts are bounded by E.

For a sparse graph with E = O(V), the binary heap implementation gives O((V + E) log V) = O((V + V) log V) = O(V log V). Options B and C both express this correctly - O(V log V) and O(E log V) are equivalent when E = O(V). This is better than O(V²) (array-based Dijkstra) for sparse graphs and motivates using heaps for sparse inputs.

1. The next server to be extracted from the priority queue (PQ) is B, as it has the minimum latency (4ms). The set of visited servers becomes {S, A, B}. The tentative distance dist[B] remains 4.

2. Now, we process the neighbors of B:

   • Neighbor A: A is already in the visited set. Therefore, we skip processing A.
   • Neighbor C: C is NOT in the visited set.
     Current dist[C] is 8ms. The path through B to C would be dist[B] + weight(B, C) = 4 + 2 = 6ms. Since 6ms < 8ms, we update dist[C] to 6ms. In the priority queue, the existing entry (8, C) is updated to (6, C).
   • Neighbor D: D is NOT in the visited set.
     Current dist[D] is infinity. The path through B to D would be dist[B] + weight(B, D) = 4 + 6 = 10ms. Since 10ms < infinity, we update dist[D] to 10ms. A new entry (10, D) is added to the priority queue.

3. After processing all unvisited neighbors of B:

   • The updated tentative distances are: dist = {S:0, A:3, B:4, C:6, D:10, E:infinity}.
   • The priority queue contains the updated entry for C and the new entry for D: PQ: {(6, C), (10, D)} (order based on latency).

Therefore, Option A is the correct answer.

This is a standard GATE-style NAT question. Given that the shortest distance is 11 and the path is unique, tracing the predecessor array from vertex 6 back to vertex 1 via the shortest path tree gives a path with 3 edges (e.g., 1→a→b→6 for some intermediate vertices). The number of edges on a shortest path equals the number of vertices on the path minus 1.

B: By definition of Dijkstra's output, every path in T from s to any vertex is a shortest path. C: T spans all reachable vertices using V-1 edges, forming a spanning tree. A: The shortest path tree and MST are different - SPT minimizes distances from a single source while MST minimizes total edge weight; they coincide only in special cases. D: Even with unique edge weights, there may be ties in shortest path distances leading to multiple valid SPTs.

Initial: d=[0,∞,∞,∞,∞]. Extract 1(d=0): relax→d[2]=10, d[3]=3. Extract 3(d=3): relax→d[2]=min(10,7)=7, d[4]=11. Extract 2(d=7): relax→d[4]=min(11,8)=8, d[5]=9. Extract 5(d=9): no improvement. Extract 4(d=8). Finalization order: 1, 3, 2, 5, 4.

Bellman-Ford uses dynamic programming by iteratively improving solutions.

For transitive closure, T^(k)[i][j] = 1 if there is a path from i to j using intermediate vertices from {1,...,k}. Either such a path already existed without k: T^(k-1)[i][j] = 1, OR a path from i to k exists (T^(k-1)[i][k] = 1) AND a path from k to j exists (T^(k-1)[k][j] = 1). Combined: T^(k)[i][j] = T^(k-1)[i][j] OR (T^(k-1)[i][k] AND T^(k-1)[k][j]). This replaces min with OR and addition with AND.

Any negative weight edge, whether incident to u or not, can break Dijkstra's correctness. A negative edge not incident to u may create a shorter path to u through another vertex that hasn't been finalized yet. A negative edge incident to u (as an incoming edge) could provide a shorter path once that edge's source is finalized later. Positive-weight cycles and multi-edges with positive weights do not affect correctness.

If no updates occur, algorithm can terminate early as shortest paths are found.

In the worst case, every edge (u, v) causes a relaxation that successfully updates d[v], triggering a decrease-key operation on v in the priority queue. Since there are E edges in the graph, the maximum number of decrease-key operations is E. Combined with V extract-min operations, total complexity is O((V + E) log V) with a binary heap.

When a negative cycle exists: A: D[i][i] < 0 for vertices on the cycle - the standard detection condition. B and D: For any vertex i that can reach the cycle and any vertex j reachable from the cycle, the 'shortest path' from i to j is -∞ because the cycle can be traversed arbitrarily many times to reduce the path weight without bound. C is FALSE: Floyd-Warshall always terminates after exactly n³ iterations regardless of negative cycles.

Dijkstra is faster and preferred when no negative edges exist.

When the shortest path from i to j is not updated (direct path is still better), the predecessor remains π^(k-1)[i][j]. When the path through k is shorter (D^(k-1)[i][k] + D^(k-1)[k][j] < D^(k-1)[i][j]), the predecessor of j on the new path becomes π^(k-1)[k][j] - the predecessor of j on the path from k to j. To reconstruct path i→j, follow π back from j.

After k iterations, shortest paths with at most k edges are guaranteed.

Each edge can be relaxed at most V-1 times in worst case.