Book edition 7th

Author(s) Kenneth H. Rosen

Pages 808 pages

ISBN 9780073383095

Answers without the blur.

Just sign up for free and you're in.

Short Answer

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}}\)

See the step by step solution

Step by Step Solution

TABLE OF CONTENTS :

TABLE OF CONTENTS

Step 1: Given data

The shortest path between two vertices in a directed graph.

Step 2: Concept used of algorithm

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

Step 3: Warshall algorithm

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).

Step 4: Determine the 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\).

Find Study Materials for

Create Study Materials

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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.

Step by Step Solution

Step 1: Given data

Step 2: Concept used of algorithm

Step 3: Warshall algorithm

Step 4: Determine the path

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Select your language

Discrete Mathematics and its Applications

Answers without the blur.

Short Answer

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.

Step by Step Solution

Step 1: Given data

Step 2: Concept used of algorithm

Step 3: Warshall algorithm

Step 4: Determine the path

Most popular questions for Math Textbooks

Want to see more solutions like these?

Recommended explanations on Math Textbooks

Decision Maths

Calculus

Probability and Statistics

Statistics

Mechanics Maths

Geometry

Pure Maths