0.4.4 Dijkstra's Algorithm - Shortest Path
While Floyd's algorithm determines the lowest-cost path
between all vertices in a graph, Dijkstra's was designed to
find the lowest cost path between a single starting vertex
and all of the other vertices in a graph. Dijkstra's can, clearly,
be used to obtain the same information as Floyd's algorithm
if it is called repeatedly for every vertex in a graph.
Dikjstra's algorithm is a greedy algorithm which
means, if given a choice, it operates by choosing the biggest
or most valuable alternative.
The first step of this algorithm is to "label" the starting vertex
with an ordered pair, (-,0), and initialize a distance counter to one.
Next, look at all edges between labeled vertices and unlabeled
vertices. If the cost of a particular edge added to the second item
in the ordered pair of the initial vertex is equal to the distance
counter, label the terminal vertex of this edge (name_of_starting_vertex, distance_counter) and continue
this process, incrementing the distance counter by one at each
iteration and continuing until all vertices in the graph are labeled.
The second member of the ordered pair at each vertex is the lowest
cost walk from it to the starting vertex. The first member of the
ordered pair of the ordered pair is the node immediately preceding the
current node on the shortest path from source to destination.
The algorithm actually coded is implemented in a slightly different
manner. Because it is inefficient to store the distance counter and
look at every edge at every increment, I choose to begin at the
starting vertex and traverse to all nodes reachable from it. Each
node is labelled with a distance from the start and a previous
vertex. Each node is also enqueued for later processing.
Once all nodes adjacent to the starting vertex are processed, labelled
and enqueued, the algorithm dequeues the first node. All nodes
adjacent to this vertex that have not been visited are labelled and
enqueued. Additionally, any node that has been visited but can be
reached more cheaply is re-labelled and enqueued.
This process continues until the queue is empty. The shortest path to
a given vertex n is labelled on that vertex. The path can be
determined by examining the prior steps recursively back to the