Both Dijkstra’s algorithm and the Bellman–Ford algorithm find the least-cost paths from one node to all other nodes. The Floyd–Warshall algorithm finds the least-cost paths between all pairs of nodes together. Define:

N = set of nodes in the network w(i, j) = link cost from node i to node j; w(i, i) = 0; w(i, j) = ∞ if the two nodes are not directly connected Ln(i, j) = cost of the least-cost path from node i to node j with the constraint that only nodes 1, 2, …, n can be used as intermediate nodes on paths The algorithm has the following steps:

1. Initialize:

L0(i, j) = w(i, j), for all i, j, i ≠ j 2. For n = 0, 1,

c, N - 1 Ln+1(i, j) = min[Ln(i, j), Ln(i, n + 1) + Ln(n + 1, j)] for all i ≠ j Explain the algorithm in words. Use induction to demonstrate that the algorithm works.