python - Why A star is faster than Dijkstra's even the heuristic is set to be None in the networkx -


this update version of previous question. run 2 algorithm in networkx between 2 point (you can try on of network) in jupyter notebook. result shows astar faster, when heuristic none. suppose 'none' means dijkstra. wrong?

import osmnx ox import networkx nx g = ox.graph_from_place('manhattan, new york, usa', network_type='drive') #change simple network in order run astar g_simple=nx.graph(g) 

dijkstra:

%%time nx.dijkstra_path(g_simple, 42434910, 595314027,  weight='length') #the node random selected nodes in graph 

the computation time is:

cpu times: user 15.4 ms, sys: 1.86 ms, total: 17.2 ms     wall time: 17.1 ms 

astar:

%%time nx.astar_path(g_simple, 42434910, 595314027, heuristic=none, weight='length') 

the computation time is:

cpu times: user 8.8 ms, sys: 313 µs, total: 9.12 ms wall time: 9.18 ms 

the dijkstra implementation networkx using doesn't stop when reaches target node. a* implementation does.


Comments

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

python Tkinter Capturing keyboard events save as one single string -

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -