CODEWITHSUNDEEP
pythontimenetworkxdijkstraa-star
Kevin
Kevin

Reputation: 597

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

This is an update version of my previous question. I run the two algorithm in NetworkX between two point (you can try it on any of your now network) in Jupyter notebook. The result shows the astar is much faster, even when the heuristic is None. I suppose the 'None' means it is a Dijkstra. Am I wrong?

import osmnx as ox
import networkx as nx
G = ox.graph_from_place('Manhattan, New York, USA', network_type='drive')
#change to a simple network in order to run Astar
G_simple=nx.Graph(G)

Dijkstra:

%%time
nx.dijkstra_path(G_simple, 42434910, 595314027,  weight='length') #the node is random selected from nodes in the 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

Upvotes: 3

Views: 886

Answers (1)

user2357112
user2357112

Reputation: 281958

The Dijkstra implementation NetworkX is using doesn't stop when it reaches the target node. The A* implementation does.

Upvotes: 4

Related Questions