7

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 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:

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?

3

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.

  • Thank you for the answer! Yes, I put the distances of every arc as weight (just as you did). My objective is to actually compute the shortest path from each node to every other nodes given that e.g a car will go from one point to the other and return on the same route. So in this case, I think applying weights as a symbol of direction is good? Or how should I give the directions? – botibo Nov 26 '18 at 14:11
  • I already tried with the all_pairs_dijkstra_path and I think that is the one that I want to use. But currently, I still get 55000 shortest paths instead of 63756 shortest paths (I have 253 nodes so 253x(253-1)) – botibo Nov 26 '18 at 14:13
  • 1
    @botibo Re: directions, I still don't see a need for directionality. If a car goes from n1->n2, then returns via n2->n1, the total path length is just the length of n1->n2 multiplied by 2 and you already know the nodes along the path, so you can just reverse them. Re: the wrong number of nodes, is it possible that you have some nodes lying on top of others, i.e. with the same coordinates? The square root of 55,000 indicates there are roughly 234 unique nodes. – Jon Nov 26 '18 at 15:10
  • 1
    Also, you may want to double-check that all your nodes are reachable. You can do this using len(list(nx.connected_components(G))) which should be 1. – Jon Nov 26 '18 at 15:28
  • Hey! Thank you for the answers. I think you are right, I dont' quite need directions because I just measure a car that is going to a place one at a time. I've also used your method to check the nodes, and I got 4 connected components. I double checked my nodes and yes, I found some nodes that are lying on top of each others. Thank you for the answer! – botibo Nov 27 '18 at 2:48
4

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.

  • I don't quite get it, so I need to do it manually with the method? I've also tried with this networkx.github.io/documentation/stable/reference/algorithms/… But apparently, it only returns some shortest paths of each point, and also I saw infinity number as a result. – botibo Nov 25 '18 at 2:35
  • You are using the method for unweighted graph. It's wrong, because the result will be "the pass with the least crossroads". Try this: networkx.github.io/documentation/stable/reference/algorithms/… – Serge Norin Nov 25 '18 at 7:04
  • Thank you for the reference. I am trying to do that and now I am having more shortest paths, but still not all shortest paths that I want (e.g I just have 8000 paths instead of 14000-ish paths for 120 nodes that I have). Do you know why? – botibo Nov 26 '18 at 2:31
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.