• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

### Select your language

Suggested languages for you:

Americas

Europe

Q31E

Expert-verified
Found in: Page 607

### Discrete Mathematics and its Applications

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}}$$

See the step by step solution

## 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$$.