Shortest path between one point to every other points

Question

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.

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:

With that road network, I have 214 nodes (which should result in 214x214 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:

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?

Answer 1

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.

Answer 2

NetworkX all_shortest_paths or single_source_dijkstra

You need to calculate all the shortest paths from your source and then summarize edges weights fro every path. Also I'm absolutely sure that there is much simplier way to do this because Dejkstra algorithm calculates all the paths in you graph to return a single one. So you dont need to calculate it again.

Answer 3

You can skip the python part and use the plugin QNEAT3 which is available for QGIS3 (see Distance Matrix with 2 point shapefiles and one street network. It also works in your case offers multiple processing algorithms that produce origin-destination matrices (OD-Matrix) as line layer, table or csv file out of the box. It also supports n:n relations which fits to your single layer task in your question. All algorithms rely on the dijkstra() method in the qgis.analysis module, therefore all costs are calculated on the basis of shortest paths.

You can get more information about the plugin at the qgis plugin repository and at the plugins documentation.