dunitvectorstra.py

#!/usr/bin/env python

# graph https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#/media/File:Dijkstra_Animation.gif

# for example, graph[1][2] is the distance from node 1 to 2
graph = {
        1: {2:7, 3:9, 6:14},
        2: {1:7, 3:10, 4:15},
        3: {1:9, 2:10, 4:11, 6:2},
        4: {2:15, 3:11, 5:6},
        5: {4:6, 6:9},
        6: {1:14, 3:2, 5:9},
        }

# dictionary mapping nodes to distances from node 1
shortestdists = {}
# dictionary mapping shortest paths from node 1, paths are represented as lists
shortestpaths = {}

visited = set()
unvisited = set(range(1,6+1))
current = 1
currentdist = 0
currentpath = []
shortestdists[current] = 0
while unvisited:
    print current
    # find the shortest way to each adjacent node
    for (node, dist) in graph[current].items():
        newdist = currentdist + dist
        if not node in shortestdists or newdist < shortestdists[node]:
            # found a shorter distance
            print "node " + str(node) + " has dist " + str(newdist)
            shortestdists[node] = newdist
            shortestpaths[node] = currentpath + [node]
    # mark the current node as visited
    unvisited.remove(current)
    visited.add(current)
    # find the next closest node we haven't visited
    currentbestdist = 9999
    for (node, dist) in shortestdists.items():
        if node in unvisited and dist < currentbestdist:
            current = node
            currentbestdist = dist
    currentdist = shortestdists[current]
    currentpath = shortestpaths[current]

print shortestdists
print shortestpaths