from collections import namedtuple ,deque import os inf = float('inf') Edge = namedtuple('Edge', 'start, end, cost') class Graph(): def __init__(self, edges): self.edges = edges2 = [Edge(*edge) for edge in edges] self.vertices = set(sum(([e.start, e.end] for e in edges2), [])) def dijkstra(self, source, dest): assert source in self.vertices dist = {vertex: inf for vertex in self.vertices} previous = {vertex: None for vertex in self.vertices} dist[source] = 0 q = self.vertices.copy() neighbours = {vertex: set() for vertex in self.vertices} for start, end, cost in self.edges: neighbours[start].add((end, cost)) while q: u = min(q, key=lambda vertex: dist[vertex]) q.remove(u) if dist[u] == inf or u == dest: break for v, cost in neighbours[u]: alt = dist[u] + cost if alt < dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u s, u = deque(), dest while previous[u]: s.appendleft(u) u = previous[u] s.appendleft(u) return s def find_shortest_path(source,destination): graph = Graph([(e[0],e[1],e[2],) for e in data]) path = [e for e in graph.dijkstra(source, destination)] traverse = [(path[i],path[i+1]) for i in range(len(path)-1)] t_route = [(e,stop_to_route[e]) for e in traverse] return t_route if __name__=="__main__": routes = {"R1":["A","B","C","D","E","F"], "R2":["A","M","N","0"], "R3":["K","N","L","F"], "R4":["A","M","N","0"], } data =[] for route,path in routes.iteritems(): for i in range(len( path)-1): data.append( (path[i] , path[i+1] , 1 , route)) stop_to_route={} for e in data : from_to = (e[0],e[1]) if from_to not in stop_to_route: stop_to_route[from_to]= [e[3]] else: stop_to_route[from_to].append(e[3]) all_stops = [] [all_stops.extend(e) for e in routes.values()] all_stops = [e for e in set(all_stops)] print "For A to F : > " for each in find_shortest_path("A","F"): print each
Run
Reset
Share
Import
Link
Embed
Language▼
English
中文
Python Fiddle
Python Cloud IDE
Follow @python_fiddle
Browser Version Not Supported
Due to Python Fiddle's reliance on advanced JavaScript techniques, older browsers might have problems running it correctly. Please download the latest version of your favourite browser.
Chrome 10+
Firefox 4+
Safari 5+
IE 10+
Let me try anyway!
url:
Go
Python Snippet
Stackoverflow Question