Guest User

Untitled

a guest
Jan 18th, 2017
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.00 KB | None | 0 0
  1. class Graph:
  2. def __init__(self):
  3. self.nodes = set()
  4. self.edges = defaultdict(list)
  5. self.distances = {}
  6.  
  7. def add_node(self, value):
  8. self.nodes.add(value)
  9.  
  10. def add_edge(self, from_node, to_node, distance):
  11. self.edges[from_node].append(to_node)
  12. self.edges[to_node].append(from_node)
  13. self.distances[(from_node, to_node)] = distance
  14.  
  15.  
  16. def dijsktra(graph, initial):
  17. visited = {initial: 0}
  18. path = {}
  19.  
  20. nodes = set(graph.nodes)
  21.  
  22. while nodes:
  23. min_node = None
  24. for node in nodes:
  25. if node in visited:
  26. if min_node is None:
  27. min_node = node
  28. elif visited[node] < visited[min_node]:
  29. min_node = node
  30.  
  31. if min_node is None:
  32. break
  33.  
  34. nodes.remove(min_node)
  35. current_weight = visited[min_node]
  36.  
  37. for edge in graph.edges[min_node]:
  38. weight = current_weight + graph.distance[(min_node, edge)]
  39. if edge not in visited or weight < visited[edge]:
  40. visited[edge] = weight
  41. path[edge] = min_node
  42.  
  43. return visited, path
Add Comment
Please, Sign In to add comment