Shortest-path routing: Dijkstra algorithm We will use Figure 8.29 to illustrate the Dijkstra algorithm for finding the shortest route to a destination node. The length of the direct arc connecting nodes i and j is defined to be dij. For a detailed description of the figure and the definition of dij, please refer to Problem 8.4. Denote by P the set of nodes whose shortest path to the destination node is known, and denote byDj the current shortest distance from node j to the destination node. Note that only when node j belongs to the set P can we say Dj is the true shortest distance. Choose node 1 as the destination node.

Initially, set P¼{1}, D1¼0, and Dj¼1for j 6¼ 1.

(a) Update Dj for j 6¼ 1 using the following equation Dj :¼ min½Dj; dj1:

(b) Find i such that Di ¼ min j=2P

½Dj:

Update P:¼P [ {i}.

(c) Update Dj for j =2 P by the following equation Dj :¼ min½Dj;Di þ dji

in which i is the i obtained in (b).

(d) Go back and compute steps

(b) and

(c) recursively until P contains all the nodes in the network. The resulting Dj is the shortest distance from node j to node 1.