[Python] Optimize Dijkstra runtime for large NetworkX graph (300k nodes, 700k edges)

Im working with a very large networkx DiGraph consisting of approximately 300,000 nodes and 700,000 edges.

Im implementing Dijkstra's algorithm manually and Im trying to optimize its runtime.

Profiling shows that about 50% of the total runtime is spent on the following two lines:

for v in graph.neighbors(u):
cuv = adj[v]['weight']

adj = graph.adj is pre-defined for faster access.

My question: How can I make access to graph.neighbors(u) and adj[v]['weight'] faster to significantly reduce runtime? I tried a lot of things but nothing was faster than that.

Important: The graph is a directed graph All edges have a 'weight' attribute I have the nx.digraph given so i must use it

Thanks in advance!

Continue reading...