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