2.3.4. Shortest path in a connected graph

Beside the above defined measurements we can introduce a more practical index: we order to each a function and we call it as weight. The graph which edges have weights is a weighted graph. Let be a function. We extend this function to subgraphs. Let then

Many optimization problems are looking for - in a weighted graph - a certain type of subgraph with minimum (or maximum) weight.

The Shortest Path Problem: given a weighted graph (railway net-work connecting various towns), determine a shortest path (a shortest route) between two specified vertices (town in the network).

The Dijkstra algorithm (1959)

Let a function. Using the subgraph weight definition, we get:

Then the distance of two vertices in a weighted graph G is where the summation is over all in G, where P is a path between u and v.

We shall refer to the weight of a path in a weighted graph as its length.

Suppose we want to decide the distance between two vertices, u0 and v0.

- The algorithm uses a permanently (stepwise) increasing set Si, where , and and

- in each step we order a label to the vertices: so that for the label will give the distance of the vertex v from the vertex u0 within the induced subgraph .

Initial step:

 


 

Iteration step:

1. If then the algorithm terminates.

2. If then and let ui+1 an arbitrary element of W.

3. If or then the algorithm stops.

4. If then and let

5. i=i+1, goto 1.

Theorem 2.12. At the end of the Dijkstra's Algorithm the values of the labels are the shortest distances from the starting vertex.

Lemma 2.12.1. If then is the length of the shortest path. Furthermore, among the shortest paths there exists a for which if , then both and .

Proof of Lemma 2.12.1. By induction on i.

- For i = 0 he statement is true.

- Suppose that the statement is true for a given . We need to prove our statement for , since the label of the other vertices in do not change any more.

The first part of the statement follows immediately from the construction.

To prove the second part let us suppose that P is a shortest path. We can divide P into two parts: , where P1 contains only edges of , it terminates in x, and P2 has only one "outgoing" edge .

Because of the induction hypothesis the weight of the edge is . But .

Therefore each vertex of P is in .

Lemma 2.12.2. has the property that its label is the length of the shortest path whose vertices - except - are in .

Proof of Lemma 2.12.2. We consider paths in the form: , where and z is an endvertex of P. (z is arbitrary.)

Because of the Lemma 2.12.1. among the paths there is always a minimal length path for which if , then both incident vertices of e are in the actual .

The minimal length of P has changed when z was chosen as a new element of . It has been denoted by .

So, when we relabelled , then the label of x was the length of a shortest path.

When we have certain to reach , then our algorithm chooses the length of the smallest as a label for .

It is clear that the algorithm terminates in at most steps. If then we can use our lemmas, and so the algorithm is correct.

If the labels of each are equal to ∞ then there is no edge from to .

If there is an edge then the label of y would change to finite when x was chosen for .

Example:

Figure 2.9. The steps of the Dijkstra algorithm