Shortest Path Calculation – From One Point to Every Other Points Using QGIS and Python

Networknetworkxqgisshortest path

I am trying to figure out how to find all the shortest paths from each point and each node of a line to the other points and nodes of lines of this map.

enter image description here

I have tried to do it in Python using NetworkX. For testing, I clipped the map and tried to only look for the shortest paths from each node of a line to every other nodes of other lines of this map:
enter image description here

With that road network, I have 214 nodes (which should result in 214×214 shortest paths, I think). I have tried to make the graph of the road network with this code:

#Create the network graph
G = nx.DiGraph()
for k,v in idict.items():
    G.add_edge(v[0],v[1], weight = v[2]) # v[0] = first (x,y) of a linestring, v[1] = last (x,y) of a linestring, v[2] = distance
    G.add_edge(v[1],v[0], weight = v[2]) #  return path

len(G.edges())

pos = nx.spring_layout(G)
nx.draw_networkx_nodes(G, pos = pos, node_size=20,arrows = True)
nx.draw_networkx_edges(G, pos = pos)
plt.show()

And the result shows:

enter image description here

I've also tried to apply the networkx floyd warshall function to calculate all shortest paths from each point to another point but some of the results return to infinity (as I think it says that no path is found between the points, while actually all paths are connected). All in all, it only returns to about 1720 shortest paths

How should I proceed to have the shortest path of each node to every other nodes in the map?

Best Answer

You first need to define what you mean by shortest path. If you don't weight your graph (G), shortest path is simply the path that connects the nodes that passes through the fewest number of other nodes. If you want to incorporate the actual length of the lines, you need to create a weighted graph:

# Compute weights
weights = lengths of each link in idict.items # square root of sum of squares or whatever

#Create the network graph
G = nx.Graph()
for k,v, wt in zip(idict.items(), weights):
    G.add_edge(v[0],v[1], weight = wt)

Note that since your graph has apparently no directionality, you should not use a DiGraph. A regular Graph should be sufficient. Now G contains weighted links, and you can use the dijkstra algorithms to find the shortest paths.

You should look at this page for your options: https://networkx.github.io/documentation/stable/reference/algorithms/shortest_paths.html Scroll down to "Shortest path algorithms for weighed graphs."

From your question, it appears that you'll want one of the all_pairs_xxx -- which you choose depends on what output you want. If you want the actual nodes along each shortest path, use all_pairs_dijkstra_path. If you just need the lengths, use all_pairs_dijkstra_path_length. If you need both, use all_pairs_dijkstra.

Note that these functions all return an iterator--the shortest paths are not actually computed until you unpack the iterator. This means that these functions will compute very quickly, but the real heavy lifting occurs after you unpack them. You can unpack them simply:

blah = nx.all_pairs_dijkstra_path(G)
shortest_paths = list(blah)

shortest_paths should be the same length as the number of nodes in G.

Note that there is some redundancy in this approach, and I'm not sure if networkX takes advantage of the fact that the shortest path from n0->n1 is the same as n1->n0 for an undirected graph.

Related Question