Advertisement
NLinker

Dijkstra algorithm

Jul 27th, 2017
252
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.09 KB | None | 0 0
  1. from collections import defaultdict, deque
  2.  
  3. """
  4.  
  5. ~/v/H/p/s/py ❯❯❯ python3 dijkstra.py
  6. {'G', 'B', 'E', 'A', 'D', 'F', 'C'}
  7. {'A': 0}
  8. nodes={'G', 'B', 'E', 'D', 'F', 'C'} visited={'B': 10, 'C': 20, 'A': 0} min_node=A
  9. nodes={'G', 'E', 'D', 'F', 'C'} visited={'D': 25, 'E': 60, 'B': 10, 'C': 20, 'A': 0} min_node=B
  10. nodes={'G', 'E', 'D', 'F'} visited={'D': 25, 'E': 60, 'B': 10, 'C': 20, 'A': 0} min_node=C
  11. nodes={'G', 'E', 'F'} visited={'D': 25, 'E': 55, 'B': 10, 'C': 20, 'A': 0} min_node=D
  12. nodes={'G', 'F'} visited={'B': 10, 'E': 55, 'A': 0, 'D': 25, 'F': 60, 'C': 20} min_node=E
  13. nodes={'G'} visited={'B': 10, 'E': 55, 'A': 0, 'D': 25, 'G': 62, 'F': 60, 'C': 20} min_node=F
  14. nodes=set() visited={'B': 10, 'E': 55, 'A': 0, 'D': 25, 'G': 62, 'F': 60, 'C': 20} min_node=G
  15. (25, ['A', 'B', 'D'])
  16.  
  17. """
  18.  
  19.  
  20.  
  21. class Graph(object):
  22.     def __init__(self):
  23.         self.nodes = set()
  24.         self.edges = defaultdict(list)
  25.         self.distances = {}
  26.  
  27.     def add_node(self, value):
  28.         self.nodes.add(value)
  29.  
  30.     def add_edge(self, from_node, to_node, distance):
  31.         self.edges[from_node].append(to_node)
  32.         self.edges[to_node].append(from_node)
  33.         self.distances[(from_node, to_node)] = distance
  34.  
  35.  
  36. def dijkstra(graph, initial):
  37.     visited = {initial: 0}
  38.     path = {}
  39.  
  40.     nodes = set(graph.nodes)
  41.     print(nodes)
  42.     print(visited)
  43.  
  44.     while nodes:
  45.         min_node = None
  46.         for node in nodes:
  47.             if node in visited:
  48.                 if min_node is None:
  49.                     min_node = node
  50.                 elif visited[node] < visited[min_node]:
  51.                     min_node = node
  52.         if min_node is None:
  53.             break
  54.         nodes.remove(min_node)
  55.         current_weight = visited[min_node]
  56.         # enumerate all adjacent nodes of min_node
  57.         for node in graph.edges[min_node]:
  58.             try:
  59.                 weight = current_weight + graph.distances[(min_node, node)]
  60.             except:
  61.                 continue
  62.             if node not in visited or weight < visited[node]:
  63.                 visited[node] = weight
  64.                 path[node] = min_node
  65.         print("nodes=%s visited=%s min_node=%s" % (nodes, visited, min_node))
  66.  
  67.     return visited, path
  68.  
  69.  
  70. def shortest_path(graph, origin, destination):
  71.     visited, paths = dijkstra(graph, origin)
  72.     full_path = deque()
  73.     _destination = paths[destination]
  74.  
  75.     while _destination != origin:
  76.         full_path.appendleft(_destination)
  77.         _destination = paths[_destination]
  78.  
  79.     full_path.appendleft(origin)
  80.     full_path.append(destination)
  81.  
  82.     return visited[destination], list(full_path)
  83.  
  84. if __name__ == '__main__':
  85.     graph = Graph()
  86.  
  87.     for node in ['A', 'B', 'C', 'D', 'E', 'F', 'G']:
  88.         graph.add_node(node)
  89.  
  90.     graph.add_edge('A', 'B', 10)
  91.     graph.add_edge('A', 'C', 20)
  92.     graph.add_edge('B', 'D', 15)
  93.     graph.add_edge('C', 'D', 30)
  94.     graph.add_edge('B', 'E', 50)
  95.     graph.add_edge('D', 'E', 30)
  96.     graph.add_edge('E', 'F', 5)
  97.     graph.add_edge('F', 'G', 2)
  98.  
  99. print(shortest_path(graph, 'A', 'D')) # output: (25, ['A', 'B', 'D'])
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement