Straight to the Point: A Short Chapter About the Shortest Paths
András Gulyás, Zalán Heszberger, József Bı́ró · 2020
There is something compelling about shortest paths. They are so simple and reasonable. They seem to be the most efficient paths for traveling between nodes in a network. They may take the lowest amount of distance, time or energy. For grasping the idea of shortest paths, let’s consider the network in the first figure of this chapter. In this network, the shortest path between nodes D and H is the path (D → C → E → G → H) marked with red arrows. Its length is the number of edges crossed which is 4 and this is the only shortest path between D and H. Green arrows mark the shortest paths from node C to node F. There are two shortest paths (C → B → A → F) and (C → E → G → F) and both have a length of 3. Shortest paths are also pretty straightforward to compute by a few lines of code e.g., by using Edsger W. Dijkstra’s (Numer Math 1:269–271, 1959) method.