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))
def
and thewhile
, and add areturn A
at the end of the function, I can agree it seems to work. \$\endgroup\$ – Janne Karila Feb 1 '15 at 18:06