Using Dijkstra's Algorithm to Find The Shortest Path

The Problem We Want to Solve:

Say we want to find the fastest time to get from airport A to every other airport (B,C,etc.), or the cheapest way or using the least amount of fuel etc. We can represent all of the different airports as nodes of a graph and the routes between them as the weighted edges. We then want to find the shortest (i.e. lowest-cost) path in the weighted graph from the start node (Airport A) to every other node. So how do we do this? We use Dijkstra's Algorithm.

Dijkstra's Algorithm is the fastest shortest start algorithm with single starts for both directed and undirected weigthed graphs with edge weights that are non-negative and unbounded. So how does it work?

The Algorithm

  1. Create a priority queue
  2. Insert the starting node with cost 0
  3. Then, do the following while the priority queue is not empty:
    1. Remove the array with the lowest weight(highest priority) and if the destination is unvisited then:
    2. Mark the destination node as visited and store the previous node and cost
    3. For each edge from the node, add the array [current node, destination node, cost/weight] to the priority queue

An Example

  1. In our example, we start at node A and add the array [A, null, 0] to the priority queue and update our table.
  2. Next, we add the edges connected from node A to the priority queue, which are [B, A, 3] and [C, A, 2]. Since [C, A, 2] has the lowest weight in our priority queue, we dequeue it and update our table for node C with the information from our array.
  3. We then add the edges of C, which our example will just be [D, C, 8], where the cost for the edge being the weight from A to C added with the weight of C to D.
  4. We repeat the process and dequeue [B, A, 3], since it has the lowest weight, and update our table.
  5. We then add the array [D, B, 4] to our priority queue. We continue and dequeue [D, B, 4], since it has the lowest weight, and update our table. Since D has no more unvisited edges, we add nothing to the priority queue.
  6. Finally, we dequeue [D, C, 8]. But since node D has been visited, we discard the array and do nothing.
  7. Finally, since the queue is empty, we are done.
Further Reading On Wikipedia