The practical applicability of solving the problem of finding the shortest path between two nodes in a network can be motivated by considering the problem of a transportation network. Consider a network in which each node represents an airport and each edge between nodes n₁ and n₂ is weighted proportionally to the cost of flying one airplane from n ₁ to n₂. Constructing the cost of the edges is a problem in itself, so this model will assume that each cost is well known.

For concreteness, consider the simple four node network in Figure 1. Suppose an airplane at airport D must get to airport B with the minimum cost, what path should that plane take. The answer, upon inspection, is clearly the path D-C-B. However, such inspection of a massive network of airports would be nearly impossible (in 1996 there were over 13,000 airports in the United States (http://www.bts.gov/publications/north_american_transportation_in_figures/html/table_11_2.html). So, an algorithm that, in general, can derive the shortest path between two nodes would be useful. Such an algorithm exists and is called Dijkstra’s algorithm developed by Edsger Dijkstra in 1959. In fact, Dijkstra’s algorithm finds the shortest path from a given source node to all the nodes in the graph.

Dijkstra’s algorithm works as follows. First, assign a cost value to every node in the network, initializing it to zero for the source node and infinity for all other nodes. Also, mark each node as unvisited, and set the source node as the current node. For the current node, consider each node that it links to, and calculate these adjacent nodes’ cost of traveling from the source node. If this calculated cost is less than the current cost for that node, overwrite the cost. When all nodes adjacent to the current node have been considered, mark the current node as visited. Then, find the node in the network with the smallest cost that has not been marked as visited as the current node and repeat the process. When all nodes have been marked as visited, the algorithm is done.

Considering the algorithm acting on Figure 1 can be instructional. Since our problem was to find the shortest path from D to B, make D the source node and the first current node. Set the cost of A to 3 and the cost of C to 5. Since all D’s adjacent nodes have been considered, mark it as visited. A is not the node with the smallest cost. It’s only unvisited neighbor is B, who’s cost is set to 10+3=13. A is marked as visited. The minimum cost is now node C. It’s only unvisited neighbor is B. Using this path, B’s cost is 7+5=12 < 13, so B’s cost is set to 12. The algorithm has show that the shortest path from D to B is through C.

From this simple example, the utility of using computerized algorithms to calculate the shortest paths is seen, as well as a possible practical application of the Dijkstra method. (Numerische Mathematik, 1 (1959), S. 269–271. http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf )