The Art of Computer Networking by Unknown

Author:Unknown
Language: eng
Format: epub

W

1

Y

2

1

3

4

2

V

Z

X

7

Figure 7.5 Example for Dijkstra’s algorithm.

7.3.3

Dijkstra’s Algorithm

We need to take a brief detour to describe Dijkstra’s algorithm. This algorithm is used in several routing protocols to find the best route to a destination, in particular it is used in OSPF, below. Dijkstra’s algorithm is a simple way of computing shortest paths though a

network where ‘shortest’ means ‘least cost’, for whatever cost measure you have chosen.

Suppose we want to find the shortest/cheapest path between V and Z in Figure 7.5,

where the cost of each hop is as indicated. With each node we shall associate a predecessor node and the cost c of getting to that node. Also we shall mark each node as ‘determined’

or ‘undetermined’:

1. Initialize all costs to ∞, predecessor names to blank, and all to be undetermined.

2. Initialize cost of the starting node V to zero.

3. While there are any undetermined nodes:

(a) pick an undetermined node with lowest current cost and call it node C;

(b) mark C determined;

(c) for each undetermined neighbour N of C

if cost to C + cost N to C < cost to N we have found a shorter path to N via

C; make the cost of N be cost to C + cost N to C and the predecessor of N

be C

Determined nodes are those for which we definitely know the cheapest route; undeter-

mined nodes are those where we might yet find a better route.

For example:

Start with

W(∞,–)

1

Y(∞,–)

V

W

X

Y

Z

2

1

3

4

2

0

∞

∞

∞

∞

V(0,–)

Z(∞,–)

X(∞,–)

–

–

–

–

–

Undet Undet Undet Undet Undet

7

132

CHAPTER 7 / ROUTING IP

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.