Q2Design and Analysis of Algorithms

The Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in a weighted directed graph (with possible negative edges but no negative cycles). It uses Dynamic Programming with the principle: the shortest path from i to j using intermediate vertices from {1, 2, ..., k}.

Define d⁽ᵏ⁾[i][j] = weight of shortest path from i to j using only vertices {1, 2, ..., k} as intermediates. Recurrence: d⁽ᵏ⁾[i][j] = min(d⁽ᵏ⁻¹⁾[i][j], d⁽ᵏ⁻¹⁾[i][k] + d⁽ᵏ⁻¹⁾[k][j]). Base case: d⁽⁰⁾[i][j] = w(i,j) if edge exists; 0 if i=j; ∞ otherwise.

• Initialize dist[i][j] with the weight matrix (∞ for no edge, 0 for diagonal).
• For k from 1 to V (each intermediate vertex):
• For i from 1 to V:
• For j from 1 to V:
• dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
• After completion, dist[i][j] = shortest path from i to j.
• Negative cycle detection: if dist[i][i] < 0 for any i, a negative cycle exists.

Graph with 4 vertices and edges: (1→2, w=3), (1→3, w=8), (1→4, w=-4), (2→3, w=1), (2→4, w=7), (3→2, w=4), (4→3, w=2), (4→1, w=-4 is missing), (3→1, w=-5), (4→3, w=2).

Initial dist matrix (∞ = no direct edge): d[1][2]=3, d[1][3]=8, d[1][4]=-4, d[2][3]=1, d[2][4]=7, d[3][1]=-5, d[3][2]=4, d[4][3]=2. After running 3 iterations (k=1,2,3,4), d[1][2]=1, d[1][3]=3, d[1][4]=-4, d[2][1]=-4, d[2][3]=-1, d[2][4]=-5, etc. Total Time: O(V³) = O(64) for V=4.

Time Complexity: O(V³). Space: O(V²). Advantage over running Dijkstra V times: handles negative edges, simpler implementation, same asymptotic complexity for dense graphs.