Find the shortest path between each pair of vertices for a simple graph using Warshall's algorithm.

Solution:

$ W_{i l}= \begin{cases}W(e) & \text { if there in an edge e from } v_{1} \text { to } v_{i} \\ 0, & \text { if there is not edge vrom } v_{1} \text { to } v_{1}\end{cases} \\ $

distance matrix $D_{0}$ is the same as of weight matrix W explore that 0 in Weather Tama diagram) are replaced by on (a very large number)

In distance matrix $D_{1}$, keep first row and first column as $D_{D}$ and legend entries as zero. To fill other entries of $D_{1}$, apply.

$ \begin{aligned} D_{1}(2,3) &=\operatorname{Min}\left[D_{0}(2,3), D_{0}(2,1)+D_{0}(1,3]\right] \\\\ &=\operatorname{Min}[7,6+3] \\\\ &=\operatorname{Min}[7,10] \\\\ &=7 \\\\ D_{1}(2,4) &=\operatorname{Min}\left[D_{0}(2,4), D_{0}(2,1)+D_{0}(1,4)\right] \\\\ &=\operatorname{Min}[\infty, 6+8] \\\\ &=\operatorname{Min}[\infty, 14] \\\\ &=14 \\\\ &=\operatorname{Min}\left[D_{0}(3,2), D_{0}(3,1)+D_{0}(1,2)\right] \\\\ &=\operatorname{Min}[\infty, \infty+5] \\\\ &=\infty \\\\ D_{1}(3,2) &=\operatorname{Min}\left[D_{0}(3,4), D_{0}(3,1)+D_{0}(1,4)\right] \\\\ &=\operatorname{Min}[2, \infty+8] \\\\ &=2 \\\\ D_{1}(3,4) &=2 \\\\ D_{1}(4,3) &=\operatorname{Min}\left[D_{0}(4,3), D_{0}(4,1)+D_{0}(1,3)\right] \\ \end{aligned} $

$ =\operatorname{Min}[\infty, 6+3] \\ $

$ =9 \\ $

Similarly to find $D_{2}$ from $D_{1}$, keep the second row and second column of $D_{1}$ as it is and diagonal entries as zero. To fill other entries apply,

$ \mathrm{D}_{2}(1,3)=\mathrm{Min}\left[\mathrm{D}_{1}(1,3), \mathrm{D}_{1}(1,2)+\mathrm{D}_{1}(2,3)\right] \\ $

$ =\operatorname{Min}[3,5+7]=3 \\ $

$ D_{2}(1,4)=\operatorname{Min}\left[D_{1}(1,4), D_{1}(1,2)+D_{1}(2,4)\right] \\ $

$ =\operatorname{Min}[8,5+11]=8 \\ $

$ D_{2}(3,1)=M$ in $\left[D_{1}(3,1), D_{2}(3,2)+D_{1}(2,1)\right] \\ $

$ =\operatorname{Min}[\infty, \infty+6]=\infty \\ $

$ D_{2}(3,4)=\operatorname{Min}\left[D_{1}(3,4), D_{1}(3,2)+D_{1}(2,4)\right] \\ $

$ =\operatorname{Min}[2, \infty+14\}=2 \\ $

$ \mathrm{D}_{2}(4,1)=\operatorname{Min}\left[\mathrm{D}_{1}(4,1), \mathrm{D}_{\mathrm{a}}(4,2)+\mathrm{D}_{1}(2,1)\right] \\ $

$ =\operatorname{Min}[6,11+6]=6 \\ $

$ D_{2}(4,3)=\operatorname{Min}\left[D_{1}(4,3), D_{1}(4,2)+D_{1}(2,3)\right] \\ $

$ =\operatorname{Min}[9,11+7]=9 \\ $

$ \begin{array}{llll}1 & 2 & 3 & 4\end{array} \\ $

Similarly to find $D_{3}$ from $D_{2}$, keep the third row and third column of $D_{2}$ unchanged and diagonal entries as zero. To find other entries apply,

$ \mathrm{D}_{3}(1,2)=\mathrm{Min}\left(\mathrm{D}_{2}(1,2), \mathrm{D}_{2}(1,3)+\mathrm{D}_{2}(3,2)\right\} \\ $

$ =\operatorname{Min}[5,3+\infty]=5 \\ $

$ D_{3}(1,4)=\operatorname{Min}\left[D_{2}(1,4), D_{2}(1,3)+D_{2}(3,4)\right] \\ $

$ =\operatorname{Min}[8,3+2]=5 \\ $

$ D_{3}(2,1)=\operatorname{Min}\left[D_{2}(2,1), D_{2}(2,3)+D_{2}(3,1)\right] \\ $

$ =\operatorname{Min}[6,7+\infty]=6 \\ $

$ D_{3}(2,4)=\operatorname{Min}\left[D_{2}(2, A), D_{2}(2,3)+D_{2}(3,4)\right] \\ $

$ =\operatorname{Min}[14,7+2]=9 \\ $

$ D_{3}(4,1)=\operatorname{Min}\left[D_{2}(4,1), D_{2}(4,3)+D_{2}(3,1)\right] \\ $

$ =\operatorname{Min}[6,9+\infty]=6 \\ $

$ D_{3}(4,2)=\operatorname{Min}\left[D_{2}(4,2), D_{2}(4,3)+D_{2}(3,2)\right] \\ $

$ =\operatorname{Min}[11,9+\infty]=11 \\ $

To find $D_{4}$ from $D_{3}$, keep the fourth row and fourth column of $D_{3}$ unchanged and diagonal entries as zero. To find other entries apply.

$ \begin{aligned} D_{4}(1,2) &=\operatorname{Min}\left[D_{3}(1,2), D_{3}(1,4)+D_{3}(4,2)\right] \\\\ &=\operatorname{Min}[5,5+11]=5 \\ \end{aligned} $

$ \begin{aligned} D_{4}(1,3) &=\operatorname{Min}\left[D_{3}(1,3), D_{3}(1,4)+D_{3}(4,3)\right] \\\\ &=\operatorname{Min}[3,5+9]=3 \\\\ D_{4}(2,1) &=\operatorname{Min}\left[D_{3}(2,1), D_{3}(2,4)+D_{3}(4,1)\right] \\\\ &=\operatorname{Min}[6,9+6]=6 \\\\ D_{4}(2,3) &=\operatorname{Min}\left[D_{3}(2,3), D_{3}(2,4)+D_{3}(4,3)\right] \\\\ &=\operatorname{Min}[7,9+9]=7 \\\\ D_{4}(3,1) &=\operatorname{Min}\left[D_{3}(3,1), D_{3}(3,4)+D_{3}(4,1)\right] \\\\ &=\operatorname{Min}[\infty, 2+6]=8 \\\\ D_{4}(3,2) &=\operatorname{Min}\left[D_{3}(3,2), D_{3}(3,4)+D_{3}(4,2)\right] \\\\ &=\operatorname{Min}[\infty, 2+11]=13 \\ \end{aligned} $

Now $D_4$ is the matrix of the shortest path between the vertices.