Dijkstra’s Algorithm – The Closest Look
Whenever there is a hard job to be done I assign it to a lazy man; he is sure to find an easy way of doing it.
Chapter 20 introduced Dijkstra’s algorithm. Here, we take a closer look at its workings, picking up the example we’ve been using of the airline flight plan. We use the algorithm to first determine the shortest among the links directly connected to the origin, so as to find the destination closest to it. Then we determine the shortest of the remaining links, as well as those directly connected to the previously identified closest destination, thereby finding the next ...