mileage = [("Saint Peter",13.4,"Mankato"), ("Saint Peter",40.8,"Faribault"), ("Mankato",35.3,"Wells"), ("Mankato",42.8,"Owatonna"), ("Faribault",16.4,"Owatonna"), ("Faribault",31.2,"Zumbrota"), ("Zumbrota",23.7,"Rochester"), ("Owatonna",43.1,"Rochester"), ("Wells",23.4,"Albert Lea"), ("Owatonna",33.5,"Albert Lea"), ("Albert Lea",22.1,"Austin"), ("Owatonna",35.2,"Austin"), ("Austin",58.4,"Cresco"), ("Austin",32.1,"Spring Valley"), ("Spring Valley",16.5,"Preston"), ("Rochester",27.6,"Spring Valley"), ("Rochester",36.5,"Preston"), ("Cresco",21.0,"Decorah"), ("Preston",35.4,"Decorah")] def shortestPathBF(edges, start, end): # Bellman-Ford algorithm d = {} # d[v] is current best known distance to v p = {} # p[v] is current best known predecessor of v for v0, w, v1 in edges: d[v1] = float('inf') d[start] = 0 for i in range(len(d)-1): for v0, w, v1 in edges: d1 = d[v0] + w if d1 < d[v1]: d[v1] = d1 p[v1] = v0 for v0, w, v1 in edges: d1 = d[v0] + w if d1 < d[v1]: raise ValueError("Negative weight cycle in the graph") path = [] v = end while True: path.append(v) if v == start: break v = p[v] path.reverse() return d[end], path def shortestPathD1(edges, start, end): # Dijsktra's algorithm, version 1 d = {} # d[v] is current best known distance to v p = {} # p[v] is current best known predecessor of v for v0, w, v1 in edges: d[v1] = float('inf') d[start] = 0 frontier = set() frontier.add(start) while len(frontier) != 0: minD, minV = min((d[v], v) for v in frontier) ## print(minD, minV) frontier.remove(minV) for v0, w, v1 in edges: if v0 == minV: d1 = d[v0] + w if d1 < d[v1]: frontier.add(v1) d[v1] = d1 p[v1] = v0 path = [] v = end while True: path.append(v) if v == start: break v = p[v] path.reverse() return d[end], path def shortestPathD2(edges, start, end): # Dijsktra's algorithm, version 2 d = {} # d[v] is current best known distance to v p = {} # p[v] is current best known predecessor of v outEdges = {} # outEdges[v] is a list of the edges out from v: (w, v1) for v0, w, v1 in edges: d[v1] = float('inf') if v0 not in outEdges: outEdges[v0] = [(w, v1)] else: outEdges[v0].append((w, v1)) d[start] = 0 frontier = set() frontier.add(start) while len(frontier) != 0: minD, minV = min((d[v], v) for v in frontier) ## print(minD, minV) frontier.remove(minV) for w, v1 in outEdges.get(minV, []): v0 = minV d1 = d[v0] + w if d1 < d[v1]: frontier.add(v1) d[v1] = d1 p[v1] = v0 path = [] v = end while True: path.append(v) if v == start: break v = p[v] path.reverse() return d[end], path from SkipList import SkipList def shortestPathD3(edges, start, end): # Dijsktra's algorithm, version 3 d = {} # d[v] is current best known distance to v p = {} # p[v] is current best known predecessor of v outEdges = {} # outEdges[v] is a list of the edges out from v: (w, v1) for v0, w, v1 in edges: d[v1] = float('inf') if v0 not in outEdges: outEdges[v0] = [(w, v1)] else: outEdges[v0].append((w, v1)) d[start] = 0 frontier = SkipList() # key: (d[v], v), value: None frontier[d[start], start] = None while len(frontier) != 0: (minD, minV), n = frontier.min() ## print(minD, minV) del frontier[minD, minV] for w, v1 in outEdges.get(minV, []): v0 = minV d1 = d[v0] + w if d1 < d[v1]: if (d[v1], v1) in frontier: ## print("improving", v1, "from", d[v1], "to", d1) del frontier[d[v1], v1] frontier[d1, v1] = None d[v1] = d1 p[v1] = v0 path = [] v = end while True: path.append(v) if v == start: break v = p[v] path.reverse() return d[end], path def allPairs(edges): # return table of distances for all pairs of vertices vertices = set() for v0, w, v1 in edges: vertices.add(v0) vertices.add(v1) vertices = list(vertices) # so that we have a consistent order d = {} # d[v0,v1] is the current best known distance from v0 to v1 for v0 in vertices: for v1 in vertices: d[v0,v1] = float('inf') for v in vertices: d[v,v] = 0 for v0, w, v1 in edges: d[v0,v1] = w for vi in vertices: # For any two vertices v0, v1, we know that d[v0,v1] is the shortest # distance between v0 and v1 if we restrict our attention to paths # where the only intermediate vertices allowed are ones prior to # vi on the list of vertices. for v0 in vertices: for v1 in vertices: d[v0,v1] = min(d[v0,v1], d[v0,vi] + d[vi,v1]) # We know the same thing as before, but also allowing vi. return d