Routing along streets uses a connected network of lines, which is called a graph. The lines in the graph can have impedance values, which discourage a routing algorithm from including them in a route. Examples of impedance values often include traffic volume, speed limit, or even distance. A key requirement for a routing graph is that all of the lines, known as edges, must be connected. Road datasets that are created for mapping will often have lines whose nodes do not intersect.
In this example, we'll calculate the shortest route through a graph by distance. We'll use a start and end point, which are not nodes in the graph, meaning we'll have to first find the graph nodes that are the closest to our start and destination points.
To calculate the shortest route, we'll use a powerful pure Python graph library called NetworkX. NetworkX is...