StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q31E

Expert-verifiedFound in: Page 607

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**To determine an algorithm using the concept of interior vertices in a path to find the length of the shortest path between two vertices in a directed graph, if such a path exists.**

procedure Length \(\left( {{M_R}:} \right.\) zero-one \(n*n\) matrix)

for a: \( = 1\) to \({\rm{n}}\)

if \(_{{\rm{i}}j} = 0\) then

\({W_{ij}}: = + \infty \)

else

\({{\rm{w}}_{{\rm{ij}}}}: = 1\)

for k: \( = 1\) to \({\rm{n}}\)

for i: \( = 1\) to \({\rm{n}}\)

for j: \( = 1\) to \({\rm{n}}\)

\({{\rm{w}}_{{\rm{ij}}}}: = \min \left( {{w_{ij}},{w_{ik}} + {w_{kj}}} \right)\)

return \({\rm{W}}\)

The shortest path between two vertices in a directed graph.

**Algorithms are used as specifications for performing ****calculations and data processing**.

We adjust the Warshall algorithm to determine the length of the shortest path.

Warshall Algorithm procedure Warshall \(\left( {{M_R}:zero - onen*n} \right.\) matrix)

\(W: = {M_R}\) fork: \( = 1\) to \(n\)

for i: \( = 1\) to \(n\)

for j: \( = 1\) to \(n\)

\({w_{ij}}: = wij \vee \left( {{w_{ik}} \wedge {w_{kj}}} \right)\)

return W

We call the algorithm "length" and the input is a zero-one matrix.

procedure Length ( \({M_R}:\) zero-one \(n*n\) matrix)

If the matrix contains a 1 for the element \({m_{ij}}\left( {{M_R} = \left( {{m_{ij}}} \right)} \right)\), then the shortest path has length 1 (as there is a direct path).

If the matrix contains a 0 for the element \({m_{ij}}\left( {{M_R} = \left( {{m_{ij}}} \right)} \right)\), then the shortest path has length greater than 1 .

We will initialize the length as \( + \infty \) when the element is 0 (where \( + \infty \) will indicate that there is no path).

The matrix W will keep track of the length of the shortest path between each pair of vertices.

for a: \( = 1\) to \(n\) if m \({m_{ij}} = 0\) then

\({w_{ij}}: = + \infty \)

else

\({W_{ij}}: = 1\)

For every possible triple \((a,b,c)\), we will then determine if there is a path from a to \(b\) that pass through vertex \(c\) alone (which is the case if \((a,c)\) and \((c,b)\) have already lengths assigned to them).

for k: \( = 1\) to \(n\)

for i: \( = 1\) to \(n\)

for j: \( = 1\) to \(n\)

\({w_{ij}}: = \min \left( {{w_{ij}},{w_{ik}} + {w_{kj}}} \right)\)

Finally we return the matrix \(W\) which contains the minimum length between each pair of vertices.

A length of \( + \infty \) means there is no path between the corresponding pair of vertices return W Thus, we have procedure Length ( \({M_R}:\) zero-one \(n*n\) matrix)

for a: \( = 1\) to \(n\)

If m \(_{{\bf{i}}j} = 0\) then

\({W_{ij}}: = + \infty \)

else

\({w_{ij}}: = 1\)

for k: \( = 1\) to \(n\)

A length of \( + \infty \) means there

return W Thus, we have procedure

for a: \( = 1\) to \(n\)

if m \({{\rm{m}}_{{\rm{ij}}}} = 0\) then

\({{\rm{w}}_{{\rm{ij}}}}: = + \infty \)

else

\({w_{{\rm{ij}}}}: = 1\)

for k: \( = 1\) to \({\rm{n}}\)

for i: \( = 1\) to \({\rm{n}}\)

for j: \( = 1\) to \({\rm{n}}\)

\({w_{{\rm{ij}}}}: = \min \left( {{w_{ij}},{w_{ik}} + {w_{kj}}} \right)\)

return \({\rm{W}}\)

for i: \( = 1\) to \(n\)

for j: \( = 1\) to \(n\)

\({w_{ij}}: = \min \left( {{w_{ij}},{w_{ik}} + {w_{kj}}} \right)\)

return \(W\).

94% of StudySmarter users get better grades.

Sign up for free