6.2.1 Shortest Paths From a Given Node to All Other Nodes [t(i, j) 2 0]

The first problem that we shall examine is that of finding the shortest path between a given node and all other nodes on a given graph G(N, A). It is assumed that all link lengths, (i, j) are nonnegative.

The algorithm basically consists of beginning at the specified node s (the "source" node) and then successively finding its closest, second closest, third closest, and so on, node, one at a time, until all nodes in the network have been exhausted. This procedure is aided by the use of a two-entry label, (d(j), p(j)), for each node j.

In the evolution of the algorithm, each node can be in one of two states:

  1. In the open state, when its label is still tentative; or
  2. In the closed state, when its label is permanent.

At any stage in the algorithm, the label entries for node j contain the following:

d(j) = length of the shortest path from s to j discovered so far
p(j) = immediate predecessor node to j in the shortest path from s to j discovered so far

Finally, we shall use the symbol k to indicate the most recent (i.e., the last) node to be closed and the dummy symbol "*" to indicate the predecessor of the source node s.

The algorithm can now be described as follows:

First Shortest-Path Algorithm (Algorithm 6.1)

STEP 1 To initialize the process set d(s) = O. p(s) = *; set d(j) = , p(j) = -for all other nodes j s; consider node s as closed and all other nodes as open; set k = s (i.e., s is the last closed node).
STEP 2 To update the labels, examine all edges (k, j) out of the last closed node; if node j is closed, go to the next edge; if node j is open, set the first entry of its label to

d(j) = Min [d(j), d(k) + (k,i)] (6.1)

STEP 3 To choose the next node to close, compare the d(j) parts of the labels for all nodes that are in the open state. Choose the node with the smallest d(j) as the next node to be closed. Suppose that this is node i.
STEP 4 To find the predecessor node of the next node to be closed, i, consider, one at a time, the edges (j, i) leading from closed nodes to i until one is found such that

d(i) - {(a, i) = d(j)

Let this predecessor node be j*. Then set p(i) = j*.

STEP 5 Now consider node i as a closed node. If all nodes in the graph are closed, then stop; the procedure is finished. If there are still some open nodes in the graph, set k = i and return to Step 2.

Upon termination of the algorithm, the d(j) part of the label of node j indicates the length of the shortest path from s to j, while thep(j) part indicates the predecessor node to j on this shortest path. By tracing back the pa j) parts, it is easy to identify the shortest paths between s and each of the nodes of G.

Notes
  1. Ties in Step 3 can be broken arbitrarily [i.e., when two or more nodes have equal d(j) and thus qualify as the next nodes to be closed, choose one among them arbitrarily]. The same applies for ties for the predecessor node in Step 4.
  2. The algorithm is easy to carry out in tableau form and especially simple for computer implementation. When using the algorithm for manual solutions, the procedure can be speeded up considerably by carrying out Steps 2-4 almost simultaneously and virtually by inspection.
  3. The algorithm can also be used for finding the shortest path between a source node and a specified terminal node. All that need be changed is Step 5: termination now occurs as soon as the terminal node becomes closed.
  4. The algorithm can be used with directed, undirected, or mixed graphs, as long as (i, j) 0 for all (i, j) A.
  5. This algorithm--or, more exactly, a minor variation of it--is generally attributed to Dijkstra [DIJK 59], but many very similar algorithms have been proposed by a number of researchers over the years.
Example 1

Consider the mixed graph shown in Figure 6.3 and suppose that the source node is a. We wish to find the shortest paths from a to all the other nodes.





Solution

Figure 6.4a shows the labels on the nodes on completion of the first pass over the five steps of the algorithm. Node b is the next node to be closed; hence after this pass k = b. The two closed nodes up to this point, a and b are indicated by a " +" next to their labels. These two labels are thus permanent. [It is advisable in manual solutions to use a special symbol (such as the " + ") to keep track of the closed nodes.]

Figure 6.4b shows the status of the network's nodes after completion of the second pass over the algorithm. The label of fhas changed, the label of c remained unchanged (why?), dis the next closed node, and k = dat the end of the pass.

Let us now trace in some detail what happens during the third pass. The edges out of d to open nodes are (d, c) and (d, g). For c we have

d(c) = Min [d(c), d(d) + 4(d, c)] = Min [8, 5 + 2] = 7

Thus, d(c) is changed from 8 to 7. We also change d(g) to 9 (from ). We now find that

Min [d(c), d(e), d(f), d(g), d(h), d(i), d(j)] = Min [7, Do, 10, 9, , , ]
= 7
= d(c)

Thus, c will be closed next. The edges to c from closed nodes are (b, c), (a, c), and (d, c). Checking, we find that d(c) - (d, c) = 7 - 2 = 5 = d(d). Therefore, we set p(c) = d (i.e., the predecessor of c is d). Since there are still some open nodes, we set k = c to complete this pass through the algorithm. The status of the graph at this point is shown in Figure 6.4c.

Proceeding in the same way, and after six more passes, we finally complete this work and reach the status shown in Figure 6.4d. The labels now contain all necessary information about the shortest path from a to every other node on the graph. For instance, the shortest path from a to h is of length 15 and [working backward from p(h) to p(e) to p(i), etc.] that shortest path is {a, d, g, i, e, A}. The tree that contains all the shortest paths out of node a is now shown in Figure 6.5.

Trees like the one sh2own in Figure 6.5 are often referred to as shortest-path trees.