Shortest Path Algorithm
1. Dijktstra's Algorithm:
At the end each node will be labeled (see Figure.1) with its
distance from source node along the best known path. Initially, no paths are
known, so all nodes are labeled with infinity. As the algorithm proceeds and
paths are found, the labels may change reflecting better paths. Initially, all
labels are tentative. When it is discovered that a label represents the shortest
possible path from the source to that node, it is made permanent and never
changed thereafter.
Look at the weighted undirected graph of
Figure.1(a), where the
weights represent, for example, distance. We want to find shortest path from A
to D. We start by making node A as permanent, indicated by a filled in circle.
Then we examine each of the nodes adjacent to A (the working node), relabeling
each one with the distance to A. Whenever a node is relabeled, we also label it
with the node from which the probe was made so that we can construct the final
path later. Having examined each of the nodes adjacent to A, we examine all the
tentatively labeled nodes in the whole graph and make the one with the smallest
label permanent, as shown in
Figure.1(b). This one becomes new working
node.
We now start at B, and examine all nodes adjacent to it. If the sum of the
label on B and the distance from B to the node being considered is less than the
label on the node, we have a shorter path, so the node is relabeled. After all
the nodes adjacent to the working node have been inspected and the tentative
labels changed if possible, the entire graph is searched for the tentatively
labeled node with the smallest value. This node is made permanent and becomes
the working node for the next round. The
Figure. 1 shows the first five
steps of the algorithm.