5
\$\begingroup\$

I am trying to implement Dijkstra without writing lot of code for the Graph class itself. I have implemented it from Wikipedia. However, I am not fond of the way I have handled the minimum distance calculation. I would like to have some improvement on that.

graph = {'s': {'v':1,'w':4 },
         'v': {'w':2,'t':6},
         'w': {'t':3},
         't': {'': None}
         }
def dj(graph, start):
    Q = []# queue to hold all the vertices
    dist = {} #dictionary to hold all the distance
    prev = {} #dictionary to hold all the previous node visited

    for key in graph.keys():
        dist[key] = 1000
        prev[key] = ""
        Q.append(key)


    dist[start] = 0

    #I had to have another distance data structure dst
    # to store all the distance covered
    # I am not fond of it
    dst = []

    while Q:
        # Here I get the minimum distance
        u = min(dist, key = dist.get)
        # remove the min one from Q
        Q.remove(u)
        for v in graph[u]:
            #I also want to improvise this condition block
            #It is because of 't': {'': None} 
            if graph[u][v] is None:
                continue
            alt = dist[u] + graph[u][v]
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
        #I have to discard the minimum key from dist dictionary
        d = (dist.pop(u))
        # I then have to append the discarded one to dst dictionary
        # Redundant work
        dst.append(d)

    return dst,prev

print(dj(graph,'s'))
\$\endgroup\$
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Jan 23 '18 at 18:21
  • \$\begingroup\$ Sorry - no problem . \$\endgroup\$ – motiur Jan 23 '18 at 18:22
  • \$\begingroup\$ Your implementation is not correct as it throws on larger graphs. I am not answering, but you could take a look at this implementation. It's a point-to-point version, but may be easily modified to do the single-source shortest paths. \$\endgroup\$ – coderodde Jan 23 '18 at 19:57
3
\$\begingroup\$
    for key in graph.keys():
        dist[key] = 1000

Why 1000? There are two values which are easy to defend here: positive infinity (which is the value that an algorithms textbook would use), or half the maximum value of the datatype (to avoid overflow when adding two weights). Even the second one of those requires a comment to justify it.

        prev[key] = ""

Why not just leave it undefined?

        Q.append(key)

What is the purpose of Q? It just seems to duplicate dist.keys().


    #I had to have another distance data structure dst
    # to store all the distance covered

Why? It's not used anywhere that I can see.


        # Here I get the minimum distance
        u = min(dist, key = dist.get)

Hopefully you can see that this is quite inefficient, and that's the motivation for using more sophisticated data structures.


            #I also want to improvise this condition block
            #It is because of 't': {'': None} 
            if graph[u][v] is None:
                continue

Why is it not just 't': {}?

\$\endgroup\$
  • \$\begingroup\$ u = min(dist, key = dist.get) - should I use a heap? \$\endgroup\$ – motiur Jan 23 '18 at 18:27
  • \$\begingroup\$ More precisely, you're using a rather inefficient heap, and you should think about using a more efficient one. If you're doing this as a learning exercise you could work your way through simple binary heap, Fibonacci heap, and maybe something really exotic. \$\endgroup\$ – Peter Taylor Jan 23 '18 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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