Question

You are given a strongly connected directed graph $\mathbf{G}\mathbf{=}\mathbf{(}\mathbf{V}\mathbf{,}\mathbf{E}\mathbf{)}\mathbf{}$ with positive edge weights along with a particular${\mathbf{v}}_{\mathbf{0}}\mathbf{\in }\mathbf{V}$ . Give an efficient algorithm for finding shortest paths between all pairs of nodes, with the one restriction that these paths must all pass through${\mathbf{v}}_{\mathbf{0}}$ _.

Short answer

All Pairs Shortest Path Algorithm is used to find the shortest distance between all pairs of nodes in a graph.

Step-by-step solution

Floyd-Warshall Algorithm

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.

Shortest distance Algorithm

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

$$\begin{gathered} \mathrm{for}\hspace{0.33em}\mathrm{all}\hspace{0.33em}(\mathrm{i},\mathrm{j})\in \mathrm{E}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em} \\ \hspace{0.33em}\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}\hspace{0.33em}\mathrm{i}=1\hspace{0.33em}\mathrm{to}\hspace{0.33em}\mathrm{n}:\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em} \\ \hspace{0.33em}\mathrm{for}\hspace{0.33em}\mathrm{j}=1\hspace{0.33em}\mathrm{to}\hspace{0.33em}\mathrm{n}:\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em}\hspace{0.33em} \\ \hspace{0.33em}\hspace{0.33em}\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.