Dijkstra's algorithm in Python

Question

I was hoping that some more experienced programmers could help me make my implementation of Dijkstra's algorithm more efficient.

So far, I think that the most susceptible part is how I am looping through everything in X and everything in graph[v].

My graph is formatted as:

g = {0:{1:2}, 1:{0:2, 2:6}, 2:{1:6}}

This is my full code, where n is the number of vertices and m is the number of edges, formatted like this:

n m v1 v2 weight ...

from sys import stdin
n, m = stdin.readline().split()
n, m = int(n), int(m)
graph = {i:{} for i in range(n)}
V = [i for i in range(n)]
# paths to themselves have zero length
for i in range(m):
 a, b, t = stdin.readline().split()
 a, b, t = int(a), int(b), int(t)
 graph[a][b] = t
 graph[b][a] = t
def Dijkstra(graph, start):
# places we've found shortest path for
X = [start]
# list of shortest path length to vertices
A = [0]*len(graph)
 while X != V:
 #Dijkstra's greedy criterion
 U = float('inf')
 W = float('inf')
 uw = float('inf')
 for v in X:
 for w in graph[v]:
 if A[v] + graph[v][w] < uw and w not in X:
 uw = A[v] + graph[v][w]
 U = v
 W = w
 X.append(W)
 try:
 A[W] = uw
 except:
 return A
A = Dijkstra(graph, 0)
B = Dijkstra(graph, n-1)
C = [A[i] + B[i] for i in range(n)]
print(max(C))

• Janne Karila: If you fix the indentation between the def and the while, and add a return A at the end of the function, I can agree it seems to work.

Answer 1

(I'm assuming the code will be changed according to the comments. Otherwise it won't run with the given example graph)

Performance issues:

• Comparing lists as in while X != V involves looping through the lists. Also, the condition is not very useful because the lists only become equal in the special case when the algorithm visits the vertices in numerical order. You could as well use while True because the exception you are catching will occur when there are no vertices left to explore.
• The w not in X check also loops through X. Making X a set would help with that.
• After visiting each vertex, the for loops go through all the edges from all visited vertices, computing the tentative distances. That's a lot of repeated work. The usual approach is to compute the tentative distances only from the vertex just visited to its neighbors and store them in a data structure that allows querying the minimum distance. In Python the heapq module is available to help with that.

Implementation using heapq:

from heapq import heappush, heappop
def Dijkstra(graph, start):
 A = [None] * len(graph)
 queue = [(0, start)]
 while queue:
 path_len, v = heappop(queue)
 if A[v] is None: # v is unvisited
 A[v] = path_len
 for w, edge_len in graph[v].items():
 if A[w] is None:
 heappush(queue, (path_len + edge_len, w))
 # to give same result as original, assign zero distance to unreachable vertices 
 return [0 if x is None else x for x in A] 

• Carlos H Romano: This is such a beautiful implementation, congrats!