current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
1

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))
share|improve this question
    
The graph is only used to show how my graphs are formatted. :) I've edited it anywho. –  bobhob314 Jan 30 at 16:40
    
The code is complete and is NOT broken. It works completely. I am trying to make it more efficient. –  bobhob314 Jan 30 at 20:13
    
I have edited my code to the entirety of what I am trying to submit. The error was probably due to the fact that I had some magic numbers somewhere. Hope you can take another look! :) Thanks, hob –  bobhob314 Feb 1 at 1:36
    
I'm not familiar with this, but I voted to reopen based on your comment so others will see it and re-evaluate it. Hope you get a good review. –  Hosch250 Feb 1 at 1:46
    
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. –  Janne Karila Feb 1 at 18:06

1 Answer 1

up vote 0 down vote accepted

(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]
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.