13.17 SHORTEST PATH IDENTIFICATION (DIJKSTRA's METHOD)

We developed a simple path-finding routine. A number of alternatives—or many in the case of a large and complex graph—may exist. In a weighted graph, it is desirable to be able to find the shortest path—the one with minimum total edge weight.

In Figure 13.6, a trip from Lesser Snoring to Sleepytown might take in Great Snoring, Little Snoring and Much Snoring, and finally the destination. The total distance is 180 + 180 + 80 + 50, which is 490.