 | Find a shortest path from S to T. |
 |
We start by assigning the temporary labels 0 to S and L to
the other vertices, where L represents a large number, larger
than the sum of all the weights in the graph. Temporary labels are written
in circles.
These are the maximum distances from S to each of the other vertices, which we will reduce as we analyse the graph.
| |||||||||||||||||||||
 |
We choose the vertex k with smallest non-permanent label,
and make the label permanent. Permanent labels are written in a square.
In this case, it is S.
We write S in the second line in the table.
| ||||||||||||||||||||||||||||
 |
Now we check the neighbours x of S to see if the weight
the edge Sx is less than the
current label for x.
If it is, then replace the old label, and entry in
the table, with this.
| ||||||||||||||||||||||||||||
 |
We choose the vertex k with smallest non-permanent label,
and make the label permanent. To find the edge which was
used to obtain that label, check back to the first row y in
which that label occured in k's column in the table. Then the
edge used was yk. In this case, it is b. We write b in the next line in the table. The first time we obtained the value 4, which is now b's permanent label, was in row S so the edge Sb was added to give us the value 4.
| |||||||||||||||||||||||||||||||||||
 |
Let k be the current vertex under consideration in our table.
We check the neighbours x of k which have not already received
a permanent label, to see if the length
of the path to k (permanent label at k)
plus the weight of the edge kx is less than the
current label for x. If it is, then we replace the old label with
this sum. In this case, we look at the neighbours of b which are a and d. First we consider a. The temporary label at a is 7, and the edge from b to a is of weight 1, so weight of path to b + weight of edge ab = 5 which is less than 7 so we replace the 7 by 5. Similarly we replace the 9 by 7 at d. As b is not adjacent to c, we can not change the label at c, and similarly we can not change the label at T.
| |||||||||||||||||||||||||||||||||||
  |
We repeat the process of assigning permanent labels and then checking for
shorter routes until T has received a permanent label. (The process
can be continued until all vertices receive a permanent label.)
The smallest label is now 5 for a which was obtained using the edge ab. We now check the neighbours of a. As the weight of the path to a plus the weight of the edge aT is less than L, we replace L. a is not adjacent to any of the other vertices which have not received a permanent label so we can not change their labels. Continuing this process, we obtain the table below.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| 1 |  |
2 |  |
| 3 |  |
4 |  |
