$19\mathrm{.}12$ 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

$L_n(i,j)=$ cost of the least$-$cost path from node $i$ to node $j$ with the constraint that only nodes $1,2,$dots,$n$ can be used as intermediate nodes on paths

The algorithm has the following steps:

Initialize:

$L_0(i,j)=w(i,j),$ for all $i,j,ij$

For $n=0,1,$dots,$N-1$

$L_{n+1}(i,j)=$min$[L_n(i,j),L_n(i,n+1)+L_n(n+1,j)]$ for all $ij$

Explain the algorithm in words. Use induction to demonstrate that the algorithm works