import minPriorityQueue d = {} # empty dictionary # g must be a dictionary, hashing ints to lists of ints def numEdges(g): numEdges = 0 for v in g.keys(): numEdges += len(g[v]) return numEdges / 2 # We do Dijkstra's algorithm (usually) on a weighted graph wg = {'A':{'H':6, 'B':5}, 'B':{'C':5,'E':3,'A':5},\ 'C':{'G':4,'D':2,'B':5},\ 'D':{'C':2, 'F':7,'E':4},\ 'E':{'B':3, 'D':4,'F':2,'I':6,'J':9},\ 'F':{'G':9, 'D':7,'E':2},\ 'H':{'A':6, 'G':7,'I':5, 'J':8}, \ 'G':{'H':7, 'I':4, 'F':9, 'C':4},\ 'I':{'H':5, 'G':4, 'E':6, 'J':11},\ 'J':{'H':8 ,'I':11,'E':9}} # implementation of the Floyd-Warshall All Pairs Shortest Path algorithm def fw(wg): # set up the initial matrix of distances INFINITY = 1000000 dis = {} for v in wg: dis[v] = {} for w in wg: dis[v][w] = INFINITY for v in wg: dis[v][v] = 0 for w in wg[v]: dis[v][w] = wg[v][w] # Here's Floyd Warshall for v in wg: for s in wg: for t in wg: if dis[s][v] + dis[v][t] < dis[s][t]: dis[s][t] = dis[s][v] + dis[v][t] for v in wg: print(v, dis[v]) # implementation of Dijkstra's Algorithm def shortestPath(wg, start, end): INFINITY = float('inf') # Python trick for a very large number pq = minPriorityQueue.MinPriorityQueue() dis = {} # holds best distances to each node so far parent = {} # where the shortest path to a vertex comes from # put all nodes in min p.q. for v in wg: dis[v] = INFINITY pq.insert(v, dis[v]) dis[start] = 0 parent[start] = start pq.decreaseKey(start, dis[start]) while pq.notEmpty(): # Uncomment the next line to print the distances and queue # print("DIS: ", dis, "\npq: ", pq.a[1:pq.heapsize], "\n") # Extract the lowest distance vertex, and update neighbors v = pq.extractMin() # When we extract, we know the optimal distance to v for w in wg[v]: # for w in the dictionary of v's neighbors if dis[v] + wg[v][w] < dis[w]: dis[w] = dis[v] + wg[v][w] parent[w] = v pq.decreaseKey(w, dis[w]) print("The distance from ", start, " to ", end, " is ", dis[end]) node = end path = end while parent[node] != node: node = parent[node] path = node + "->" + path print("The path is ", path) print("To test, type \"shortestPath(wg, 'A', 'F')\", for example")