Chapter 6c


Network Algorithms and Transportation Routes


Technical Terms:

adjacent, breadth-first, depth-first, Dijkstra's algorithm, greedy algorithm, Hasse's algorithm, Kruskal's algorithm, minimal spanning tree, path, Prim's algorithm, rooted tree, weighted graph.

Link to Chapter 6.


Shortest Distance between Nodes in a Graph

There are several algorithms in use to find the shortest distance between two nodes in a connected weighted graph: a graph with numbers (or weights) assigned to its edges. The best known of these is probably Dijkstra's algorithm (1959).

Suppose that the nodes of a connected weighted graph have been ordered a = v0 , ..., vn = z and any edge {u,v} has a weight w{u,v}. Suppose also that one wants to find the shortest path from node a to node vi (originally the algorithm produced only the length, but a simple modification allows construction of the path, in reverse order of edges, from vi to a).

The algorithm constructs a length function L whose ultimate value L(vi ), together with a node function n(vi ) that ultimately gives the node preceding vi (i = 1 to n) in the shortest path from a to vi. A set S of nodes already processed will also be constructed.

Initialization.

Let S be the empty set. Let L(a) = 0. Let L(vi )∞ for i = 1 to n.

Note: if a computer is being used for this algorithm, one can set L(vi ) to be any number large enough that no distances will ever be that large.

Processing.

Repeat this process as long as S is not equal to the entire set of nodes.

  1. Let t be a node not in S with L(t) minimal; thus, t = a the first time through this process. Later there may be more than one choice possible for u, and there may be more than one shortest from a to a given v.
  2. Let S = S ∪{t}.
  3. For every vertex x such that x S and {t,a} is an edge if L(t) + W(t,x) < L(v)
    1. change L(x) to the new value L(t) + w(t,x) ( a shorter path from a to x has been found)
    2. set n(x) = t (this current candidate for shortest path from a to x ends with the edge {t,x}).

At the end of this algorithm L(vi) will be the length of the shortest path from a to vi, and the last edge in this shortest path will be the edge {u(vi), vi}.

We illustrate the algorithm with an example. Consider the graph shown in Figure 6c.1.

Image

Figure 6c.1

Initialization

L(a) = 0

L(b)

L(c)

L(d)

L(e)

L(f)

L(g)

Process: Step 1

x = a

L(b) = 1

n(b) = a

S = {a}

L(d) = 5

n(d) = a

Process: Step 2

x = b

L(d) = 4

n(d) = b

S = {a,b}

L(c) = 6

n(c) =b

Note: L(d) and n(d) changed from step 1.

Process: Step 3

x = d

L(c) = 5

n(c) = d

S = {a,b,d}

L(e) = 6

n(e) = d

Process: Step 4

x = c

L(f) = 9

n(f) = c

S = {a,b,d,c}

Process: Step 5

x = e

L(f) = 8

n(f) = e

S = {a,b,d,c,e}

L(g) = 11

n(g) = e

Process: Step 6

x = f

L(g) = 10

n(g) = f

S = {a,b,d,c,e,f}

Process: Step 7

x = g

S = {a,b,d,c,e,f,g}

The final graph now appears as in Figure 6c.2, with the values of the functions L and n attached to each node.

Image

Figure 6c.2.

Thus, the shortest path from a to g has length 10 = L(g), and since n(g) = f, n(f) = e, n(e) = d, n(d) = b, and n(b) = a, that path is a, b, d, e, f, g. Similarly the shortest path from a to c is the path a, b, d, c of length 5 (refer to Figure 6c.2). One can see in Figure 6c.3 the changes in the graph labeling as the algorithm proceeds.

In both Hasse's algorithm and Dijkstra's algorithm, some results can be determined at intermediate stages. Hasse's algorithm provides the shortest path of length k from one to another after k steps. Dijkstra's algorithm gives shortest paths from a to all nodes already in S at any stage.

Originally, Dijkstra's algorithm was used to find the shortest path from one given node to another given node. Since an edge might exist from any node to another, the number of steps in this algorithm is proportional to n2 (there are n(n-1)/2 possible edges). An algorithm of this type is called an O(n2) algorithm. To find all shortest paths, the original Dijkstra's algorithm would have to be performed n(n-1)/2 times, making the entire process O(n4). Hasse's algorithm is also O(n4). The modification of Dijkstra's algorithm above need only be performed n times (once for each node), making the finding of all shortest paths an O(n3) process.

There is a faster algorithm, called Floyd's algorithm, that is O(n3) immediately. However, no intermediate results in this algorithm have a natural meaning, and only lengths of paths are reduced. Further consideration of this algorithm is omitted.

When the graphs are small, speed is not important, and so intuitive algorithms are appealing. But in a graph with 10,000 nodes, an O(n3) algorithm might be 10,000 times as fast as an O(n4) algorithm. Knowing your application is important.

Figure 6c.3, below, gives an animated example of Dijkstra's algorithm. Notice that once a node becomes a member of S, its labels never change. The letter N is used in the figures in place of the symbol ∞.

After

S

Graph

Initialization

φ

Click on image to see graph clearly.

Step 1

{a}

Click on image to see graph clearly.

Step 2

{a,b}

Click on image to see graph clearly.

Step 3

{a,b,d}

Click on image to see graph clearly.

Step 4

{a,b,d,c}

Click on image to see graph clearly.

Step 5

{a,b,d,c,e}

Click on image to see graph clearly.

Step 6

{a,b,d,c,e,f}

Click on image to see graph clearly.

Step 7

{a,b,d,c,e,f,g}

Click on image to see graph clearly.

Image

Figure 6c.3.
 

Algorithms for Spanning Trees

Each algorithm assumes an ordering v0, ..., vn of the nodes of the graph and constructs a rooted tree T with root v0.

Depth-first search

  1. Let T = v0
  2. Let T = v0 ∪ {v0vi}, where i is the smallest integer such that {v0vi}is an edge.
  3. (This step is repeated as long as it is possible to add an edge to T and have it remain a tree.) Let vi be the last node previously added to T. If there are integers t such that {vivt} is an edge and T ∪ {vivt} remains a tree, let j be the smallest such t, and let T = T ∪ {vivt}.
  4. If T is a spanning tree, quit.
If not, "backtrack" to the second-last node added to T, third-last node, and so forth, until a node is reached that has an edge incident with it that can be added to T as in Step 3. Proceed as in Step 3. When T is a spanning tree, stop.

Breadth-first search

  1. Let T = v0
  2. Let T = v0 ∪ {v0vi | v0vi is an edge}. Draw all such edges as part of a rooted tree, with smaller i values to the left (Figure 6c.4).
  3. Image

    Figure 6c.4.

  4. Continue this process, adding edges from nodes at distance 1 from v0, proceeding from left to right in the rooted tree.
  5. Continue at subsequent levels of the tree if necessary until a spanning tree has been constructed.

In either case, one should view the results back in the original graph.

It should be clear that any connected graph has a spanning tree, since one can remove one edge from each circuit until no circuits exist.

Rooted spanning trees

The Depth-First Rooted Tree of the Chapter 6 Graph (Figure 6c.5).

Click on image to see associated animap.

Figure 6c.5.

The Breadth-First Rooted Tree of the Chapter 6 Graph (Figure 6c.6).

Click on image to see associated animap.

Figure 6c.6.

Minimal Spanning Trees

In a connected, weighted graph, it is possible to search for a minimal spanning tree; that is, a spanning tree such that the sum of the weights of the edges is the smallest possible among all spanning trees.

There are again two well-known algorithms. The first, due to Kruskal, seems at first to be most natural. The second, due to Prim, sees at first to be unnatural; indeed, it is not obvious it even yields a minimal spanning tree, yet it turns out to be computationally more efficient than Kruskal's algorithm and has certain appealing features in its intermediate results. Prim's algorithm is an example of what has come to be known as a greedy algorithm.

In both cases, one assumes an ordered set of nodes v0, ...,vn with a weight w(x,y) on each edge {x,y}. The ordering of the nodes is less crucial here than in the (unweighted) spanning tree case, but it is helpful in making the algorithm specific, rather than allowing choices at any stage.

For purposes of illustration, the Ann Arbor graph of Chapter 6 is included, with yet another labeling and with weights on the edges (Figure 6c.7).

Click on image to see larger graph.

Figure 6c.7.
 

Kruskal's Algorithm

It seems natural to select the edge of smallest weight possible at every opportunity. That natural selection is exactly what Kruskal's algorithm does. The aim is to construct a minimal spanning tree T.

Step 0. Let T = φ

Steps 1–N. (Select the n edges of the tree, one by one.)

Among all the edges not in T, select an edge e of smallest weight (it does not matter which one, but algorithms should be specific, as a specific one is chosen). If more than one is available, choose one whose node occurs first in the ordering. If more than one has this same node, choose the one whose second node occurs earlier in the ordering. The node selected, when added to T, must leave it without circuits. Let T = T  e.

This method clearly produces a minimal spanning tree, but a look at the intermediate steps suggests some problems. Look at Kruskal's algorithm applied to the Ann Arbor graph. Consider the first three Steps (Figure 5c.8).

Image

Figure 6c.8.

At Steps 1 and 2, two nodes were added, but at Step 3 only one node (G) was added. After Steps 2 and 3, the intermediate graph is acyclic, but it is not a tree. Indeed, the constructed graph does not become a tree (in this example) until the 17th and last edge IM is added. Moreover, the entire graph must be searched continually for edges of lowest weight. This procedure might not be a problem for a graph with 18 nodes and 27 edges, but it would be for a graph with 1000 nodes and 2000 edges.

Prim's Algorithm

Prim set out to solve all these problems at once. The graph he constructs remains a tree at all times, only one node is added at each stage, and one looks only at edges adjacent to the tree constructed at any time.

This method of looking only "locally" for edges of small weight might be viewed as "greedy." Local best choices are taken without regard for the global picture. Should such a method nonetheless give the best global result, the algorithm is known as a "greedy algorithm." Prim's algorithm is an example.

Step 0. Let T = v0.

Steps 1–N. (Add an edge and a node to the existing tree.)

Let e be the edge of smallest weight that is incident with a node of T whose addition to T leaves T a tree. (Resolve ties among possible choices as in Kruskal's algorithm.) Let T = T  e.

Note that each Step from 1 to N adds an edge and a node. It is not obvious that a minimal spanning tree is produced. Again look at Steps 1–3 for the Ann Arbor graph (Figure 6c.9).

Image

Figure 6c.9.

What is obvious is that the intermediate results are all trees, and that not as much of the graph needs to be searched for edges of small weight as was necessary in Kruskal's algorithm.

It is necessary to prove that Prim's algorithm works. The method is to find, among all minimal spanning trees, the one that agrees with the selections of Prim's algorithm for the longest time. This finding turns out to be complete agreement. Details can be found in any text on Discrete Mathematics.

Minimal spanning trees are useful in a variety of contexts. For instance, if the weights represented distances, a minimal spanning tree might provide a road network of least total mileage that connected the entire set of nodes. These might be the paved roads, the four lane roads, or the roads on which buses traveled. On the other hand, if weights represented building costs, a minimal spanning tree might provide a least cost connection among nodes.

Network algorithms have been written to minimize path distance, to create spanning trees, and to create minimal spanning trees. The type and size of application determine which algorithms are useful.