Dijkstra’s shortest path algorithm – Python Implementation

from pprint import pprint
def dijkstra(graph,start,target):
    inf = 0
    for u in graph:
        for v ,w in graph[u]:
           inf = inf + w
    dist = dict([(u,inf) for u in graph])
    prev = dict([(u,None) for u in graph])
    q = graph.keys()
    dist[start] = 0
    #helper function
    def x(v):
        return dist[v]
    #
    while q != []:
        u = min(q, key=x)
        q.remove(u)
        for v,w in graph[u]:
            alt = dist[u] + w
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
    #”way”
    trav = []
    temp = target
    while temp != start:
        trav.append(prev[temp])
        temp = prev[temp]
    trav.reverse()
    trav.append(target)
    return ” -> “.join(trav),dist[target]
graph = {
    ‘A’ : [(‘B’,20), (‘D’, 80), (‘G’, 90)],
    ‘B’ : [(‘F’, 10)],
    ‘C’ : [(‘F’, 50), (‘H’, 20)],
    ‘D’ : [(‘G’, 20), (‘C’, 10)],
    ‘E’ : [(‘B’, 50),(‘G’, 30)],
    ‘F’ : [(‘D’, 40),(‘C’, 10)],
    ‘G’ : [(‘A’, 20)],
    ‘H’ : []
    }
pprint(graph)
print
traverse, dist = dijkstra(graph,’A’,’C’)
print traverse
print “Distance:”,dist
Advertisements

Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: