91Ó°ÊÓ

The algorithm is used to compute the shortest distance between every pair of vertices in a weighted graph. A graph with all edges having a numerical weight is called a Weighted graph.

The algorithm to find the shortest path between i and j through a particular vertex between all pairs is:

$$\begin{gathered} \mathrm{for} \mathrm{all} (\mathrm{i},\mathrm{j})∈\mathrm{E}     \\  \mathrm{dist}(\mathrm{i},\mathrm{j},{\mathrm{v}}_0)=\mathrm{s}(\mathrm{i},\mathrm{j}) \end{gathered}$$

Here,$\mathrm{dist}(\mathrm{i},\mathrm{j},{\mathrm{v}}_0)$ is the distance between vertices i and j with intermediate vertex ${\mathrm{v}}_0$.

The shortest path between all pairs of vertices $(\mathrm{i},\mathrm{j})$with the intermediate node${\mathrm{v}}_0$ is calculated as:

$$\begin{gathered} \mathrm{for} \mathrm{i}=1 \mathrm{to} \mathrm{n}:      \\  \mathrm{for} \mathrm{j}=1 \mathrm{to} \mathrm{n}:         \\   \mathrm{dist}(\mathrm{i},\mathrm{j},{\mathrm{v}}_0)=\min \mathrm{dist}(\mathrm{i},{\mathrm{v}}_0,{\mathrm{v}}_0-1)+\mathrm{dist}({\mathrm{v}}_0,\mathrm{j},{\mathrm{v}}_0-1)+\mathrm{dist}(\mathrm{i},\mathrm{j},{\mathrm{v}}_0-1) \end{gathered}$$

Here, n is the number of vertices

Hence, an algorithm to find the shortest path between every node pair of a graph with one common intermediate node is obtained.