0% found this document useful (0 votes)

77 views

Shortest-Route Algorithms

This document discusses two algorithms for finding the shortest routes in networks: Dijkstra's algorithm and Floyd's algorithm. Dijkstra's algorithm finds the shortest routes from a single source node to all other nodes in the network. It works by gradually labeling nodes with the shortest distances from the source node and updating those labels if shorter paths are found. Floyd's algorithm is more general and can find the shortest routes between any two nodes in a network. The document provides examples of applying Dijkstra's algorithm to sample networks.

Uploaded by

أوكيتش شمشون

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

77 views

Shortest-Route Algorithms

Uploaded by

أوكيتش شمشون

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

You are on page 1/ 18

8/5/22, 6:36 PM Shortest-Route Algorithms

Home (https://www.brainkart.com) | | Resource Management Techniques (https://www.brainkart.com/subject/Resource-Management-Techniques_176/) | Shortest-Route

Algorithms

 Prev Page (https://www.brainkart.com/article/Examples-of-the-Shortest-Route-Applications-or-Problem_11227/)

Next Page  (https://www.brainkart.com/article/Linear-Programming-Formulation-of-the-Shortest-Route-Problem_11229/)

Chapter: Operations Research: An Introduction : Network Models

Shortest-Route Algorithms

This section presents two algorithms for solving both cyclic (i.e., containing loops) and acyclic networks:
1. Dijkstra's algorithm
2. Floyd's algorithm

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 1/18
8/5/22, 6:36 PM Shortest-Route Algorithms

File upload line Yellow file folder Pdf document

VECTOR icon with documents note icon in flat
style. Pa

Download Download Download

Shortest-Route Algorithms

This
section presents two algorithms for solving both cyclic (i.e., containing
loops) and acyclic networks:

1.
Dijkstra's algorithm

2.
Floyd's algorithm

Dijkstra's
algorithm is designed to determine the shortest routes between the source node
and every other node in the network. Floyd's algorithm
is more general because
it allows the determination of the shortest route between any two nodes in the network.

Ads by
Dijkstra's Algorithm. Let ui be the
shortest distance from source node 1 to node i, and define dij (≥0) as the length of arc (i, j). Then the
algorithm defines the
label for an immediately succeeding
Stopnode j asthis ad Why this ad?
seeing
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 2/18
8/5/22, 6:36 PM Shortest-Route Algorithms

The label
for the starting node is [0, --], indicating that the node has no predecessor.
Node labels in Dijkstra's algorithm are of two types:
temporary and permanent.
A temporary label is modified if a shorter route to a node can be found. If no better route can be found,
the status of the
temporary label is changed to permanent.

Example 6.3-4

The
network in Figure 6.15 gives the permissible routes and their lengths in miles
between city 1 (node 1) and four
other cities (nodes 2 to 5).
Determine the shortest routes between city 1 and each of the remaining four
cities.

Iteration 0. Assign

the permanent label [0, -- ] to node
1.

Iteration 1. Nodes 2 and 3 can be reached

from (the last permanently labeled) node 1. Thus, the list of labeled nodes
(temporary and permanent)
becomes

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 3/18
8/5/22, 6:36 PM Shortest-Route Algorithms

For the
two temporary labels [100, 1] and [30, 1], node 3 yields the smaller distance (u3 = 30). Thus, the status of node 3 is changed to permanent.

Iteration 2. Nodes 4
and 5 can be reached from node 3, and the list of labeled nodes becomes

The
status of the temporary label [40,3] at node 4 is changed to permanent (u4 = 40).

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy
Iteration 3. Nodes 2 and 5 can be reached
from node 4. Thus, the list of labeled nodes is updated as Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 4/18
8/5/22, 6:36 PM Shortest-Route Algorithms

Node 2's
temporary label [100, 1] obtained in iteration 1 is changed to [55,4) in
iteration 3 to indicate that a shorter route has been found through
node 4. Also,
in iteration 3, node 5 has two alternative labels with the same distance u5 = 90.

The list
for iteration 3 shows that the label for node 2 is now permanent.

Iteration 4. Only node 3 can be reached from

node 2. However, node 3 has a permanent label and cannot be relabeled. The new list of labels
remains the same
as in iteration 3 except that the label at node 2 is now permanent. This leaves
node 5 as the only temporary labeL Because node
5 does not lead to other nodes,
its status is convert-ed to permanent, and the process ends.
Ads by

Stop seeing this ad Why this ad?
Reach users ready to buy
The
computations of the algorithm can be carried out more easily on the network, as
Figure 6.16 demonstrates.
Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 5/18
8/5/22, 6:36 PM Shortest-Route Algorithms

The
shortest route between nodes 1 and any other node in the network is determined
by starting at the desired destination node and backtracking
through the nodes
using the information given by the permanent labels. For example, the following
sequence determines the shortest route from
node 1 to node 2:

(2) -> [55, 4] -> (4) -> [40, 3] -> (3) -> [30,1] -> (1)

Thus, the
desired route is 1 -> 3 -> 4 -> 2 with a total length of 55 miles.

PROBLEM
SET6.3B

1. The
network in Figure 6.17 gives the distances in miles between pairs of cities
1,2, ., . , and 8. Use Dijkstra's algorithm to find the shortest route
between
the following cities:

a. Cities
1 and 8

b. Cities
1 and 6

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 6/18
8/5/22, 6:36 PM Shortest-Route Algorithms

c. Cities
4 and 8

d. Cities
2 and 6

2. Use
Dijkstra's algorithm to find the shortest route between node 1 and every other
node in the network of Figure 6.18.

Adsofbythe following
problems:
3. Use
Dijkstr'a algorithm to determine the optimal solution of each
Stop seeing this ad Why this ad?
a. Problem
1, Set 6.3a. Reach users ready to buy Learn More
b. Problem
2, Set 6.3a.

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 7/18
8/5/22, 6:36 PM Shortest-Route Algorithms

c. Problem
4, Set 6.3a.

Floyd's Algorithm. Floyd's

algorithm is more general than Dijkstra's because it determines the shortest
route between any two nodes in the
network. The
algorithm represents an n-node network as a square matrix with n rows and
n columns.
Entry (~j) of the matrix gives the distance
dij from
node i to node j, which is finite if i is linked directly to j, and infinite
otherwise.

The idea
of Floyd's algorithm is straightforward. Given three nodes i j, and k in Figure 6.19 with the connecting distances shown on the three
arcs,
it is shorter to reach j from i passing
through k if

In this
case, it is optimal to replace the direct route from i -> j with the indirect route i -> k -> j. This
triple operation exchange is applied
systematically to the network using the
following steps:

Step 0.
Define the starting distance matrix Do and node sequence matrix So
as given below. The diagonal elements are marked with (--) to indicate
that
they are blocked. Set k = 1.

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 8/18
8/5/22, 6:36 PM Shortest-Route Algorithms

General step k. Define

row k and column k as pivot row and pivot column. Apply the triple operation to each element d jj in Dk - l , for all i and j.
If the
condition

is
satisfied, make the following changes:

a)
Create Dk by
replacing dij in Dk - 1 with djk
+ dkj

b)
Create Sk by replacing Sij in Sk-l with k. Set k = k + 1. If k = n + 1, stop;
else repeat step k.

Step k of the
algorithm can be explained by representing Dk - 1
as shown in Figure 6.20. Here, row k
and column k define the current pivot
row
and column. Row i

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 9/18
8/5/22, 6:36 PM Shortest-Route Algorithms

represents
any of the rows 1, 2, ... , and k -
1, and row p represents any of the rows k + 1, k + 2, ... , and n. Similarly, column j represents any of
the columns
1,2, ... , and k - 1, and column q represents any of the columns
k + 1, k + 2, ... , and n. The triple operation can be applied as follows.
If the sum of the elements on the
pivot row and the pivot column (shown
by squares) is smaller than the associated intersection element (shown by
a
circle), then it is optimal to replace the intersection distance by the sum of
the pivot distances.

After n steps, we can determine the shortest

route between nodes i and j from the matrices Dn and Sn using the following rules:

File upload line Yellow file folder Pdf document

VECTOR icon with documents note icon in flat
style. Pa

Download Download Download

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

a)
From Dm dij gives
the shortest distance between nodes i
and j.
https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 10/18
8/5/22, 6:36 PM Shortest-Route Algorithms

b)
From Sm
determine the intermediate node k = sij that yields the route i -> k -> j. If sik
= k and skj = j, stop; all
the intermediate
nodes of the route have been found.
Otherwise, repeat the procedure between nodes i and k, and between nodes k and j.

Example
6.3-5

For the
network in Figure 6.21, find the shortest routes between every two nodes. TIle distances (in miles) are
given on the arcs. Arc (3,5) is
directional, so that no traffic is allowed from
node 5 to node 3. All the other arcs allow two-way traffic.

Iteration
0. The
matrices Do and So give the initial representation of the
network. Do is sym-metrical, except that d33 = ¥
because no traffic is
allowed from node 5 to node 3.

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More
Iteration 1.

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 11/18
8/5/22, 6:36 PM Shortest-Route Algorithms

Set k = 1. The
pivot row and column are shown by the lightly shaded first row and first column
in the Do-matrix. The darker cells, d13 and d 32 ,
are the only ones that can be improved by the triple operation. Thus, D1 and SI are obtained from Do and So in the
following manner:

Iteration 2.

Set k = 2, as
shown by the lightly shaded row and column in D1• The tripLe oper-ation is applied to the darker cells in D1 and S1. The
resulting
changes are shown in bold
in D2 and S2.

Iteration 3.

Set k = 3, as shown by the shaded row and

column in D2. The new matrices are given by D3 and S3.

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 12/18
8/5/22, 6:36 PM Shortest-Route Algorithms

Iteration 4. Set k = 4, as shown by the shaded row and column in D3. The new matrices are given by D4
and S4.

Iteration 5. Set k = 5, as shown by the shaded row and column in D4. No further improvements are possible in this iteration.

The final
matrices D4 and S4
contain all the information needed to determine the shortest route between any
two nodes in the network. For
example, from D4, the shortest distance from node
1 to node 5 is d l5 = 12 miles. To determine the associated route,
recall that a segment (i, j)
represents a direct link only if sij = j.
Otherwise, i and j are linked through
at least one other intermediate node. Because sij = 4 != 5, the route is
initially given
as 1 -> 4 -> 5. Now, because s14
= 2 != 4, the segment'(I,4) is not a direct link, and 1 -> 4 is replaced with 1 -> 2 -> 4, and the
route 1 -> 4 -> 5 now becomes 1 -> 2 -> 4 -> 5. Next, because s12 = 2, s24 = 4, and s45 = 5, no further
"dissecting" is needed, and 1 -> 2 -> 4 -> 5
defines the shortest route.

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More
PROBLEM
SET 6.3C

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 13/18
8/5/22, 6:36 PM Shortest-Route Algorithms

1. In
Example 6.3-5, use Floyd's algorithm to determine the shortest routes between
each of the following pairs of nodes:

*(a) From node 5 to node 1.

(b) From node 3 to node 5.

(d) From
node 5 to node 2.

2. Apply
Floyd's algorithm to the network in Figure 6.22. Arcs (7,6) and (6,4) are
unidirectional, and all the distances are in miles. Determine the
shortest
route between the following pairs of nodes:

(a) From
node 1 to node 7.

(b) From
node 7 to node 1.

(c) From node 6 to node 7.

3. The
Tell-All mobile-phone company services six geographical areas. The satellite
distances (in miles) among the six areas are given in Figure
Adsthat
6.23. Tell-All
needs to determine the most efficient message routes byshould be established
between each two areas in the network.
Stop seeing this ad Why this ad?

Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 14/18
8/5/22, 6:36 PM Shortest-Route Algorithms

*4. Six
kids, Joe, Kay, Jim, Bob, Rae, and Kim, playa variation of hide and seek. The hiding place of a child is known only to a
select few of the
other children. A child is then paired with another with the
objective of finding the partner's hiding place. This may be achieved through a
chain
of other kids who eventually will lead to discovering where the
designated child is hiding. For example, suppose that Joe needs to find Kim and
that Joe knows where Jim is hiding, who in turn knows where Kim is. Thus, Joe
can find Kim by first finding Jim, who in turn will lead Joe to
Kim. The
following list provides the where-abouts of the children:

Joe knows
the hiding places of Bob and Kim.

Kay knows
the hiding places of Bob, Jim, and Rae.

Jim and
Bob each know the hiding place of Kay only.

Rae knows
where Kim is hiding.

Kim knows
where Joe and Bob are hiding.

Devise a
plan for each child to find every other child through the smallest number of
contacts. What is the largest number of contacts?

 Prev Page (https://www.brainkart.com/article/Examples-of-the-Shortest-Route-Applications-or-Problem_11227/)

Next Page  (https://www.brainkart.com/article/Linear-Programming-Formulation-of-the-Shortest-Route-Problem_11229/)

Ads by
Stop seeing this ad Why this ad?
Reach users ready to buy Learn More

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 15/18
8/5/22, 6:36 PM Shortest-Route Algorithms

File upload line Yellow file folder Pdf document

VECTOR icon with documents note icon in flat
style. Pa

Download Download Download

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Operations Research: An Introduction : Network Models : Shortest-Route Algorithms |

 Prev Page (https://www.brainkart.com/article/Examples-of-the-Shortest-Route-Applications-or-Problem_11227/)

Next Page  (https://www.brainkart.com/article/Linear-Programming-Formulation-of-the-Shortest-Route-Problem_11229/)

Resource Management Techniques (https://www.brainkart.com/subject/Resource-Management-Techniques_176/)

Anna University - All Subjects (https://www.brainkart.com/menu/anna-university/)

Anna University CSE - All Subjects (https://www.brainkart.com/menu/anna-university-cse/)

Engineering - All Subjects (https://www.brainkart.com/menu/engineering/)

Ads by
Computer Science Engineering - All Subjects (https://www.brainkart.com/menu/computer-science-engineering/)

Stop seeing this ad Why this ad?

Reach users ready to buy Learn More
Operations Research: An Introduction : Network Models

https://www.brainkart.com/article/Shortest-Route-Algorithms_11228/ 16/18
8/5/22, 6:36 PM Shortest-Route Algorithms

Network Models (https://www.brainkart.com/article/Network-Models_11224/)

Scope and Definition of Network Models (https://www.brainkart.com/article/Scope-and-Definition-of-Network-Models_11225/)

Minimal Spanning Tree Algorithm (https://www.brainkart.com/article/Minimal-Spanning-Tree-Algorithm_11226/)

Examples of the Shortest-Route Applications or Problem (https://www.brainkart.com/article/Examples-of-the-Shortest-Route-Applications-or-Problem_11227/)