Python Implementation of Dijkstra's Algorithm
We have now learned how Dijkstra's algorithm works, but we will now implement it in Python.
The input to the algorithm will be a network and a source vertex. The simplest way we can represent a network is with a weight matrix like we introduced in Chapter 8, Storage and Feature Extraction of Graphs, Trees, and Networks. For the graph in Figure 9.7, we have the following weight matrix:
Figure 9.17 – A small network and its weight matrix
In the context of a shortest-distance problem, this weight matrix may be called a distance matrix, but we will refrain from using this terminology because, as we have seen in previous sections, these shortest path problems may or may not actually refer to distances.
The output from the algorithm will be a table like the one at the upper right of Figure 9.15, giving the shortest distance from the source vertex to each of the other vertices.
The table in Figure...
