Dijkstra algorithm for finding the shortest path between two nodes. Returns a list of node id's, starting with id1 and ending with id2. Raises an IndexError between nodes on unconnected graphs.
(graph, id1, id2, heuristic=None, directed=False)
| 784 | return map |
| 785 | |
| 786 | def dijkstra_shortest_path(graph, id1, id2, heuristic=None, directed=False): |
| 787 | """ Dijkstra algorithm for finding the shortest path between two nodes. |
| 788 | Returns a list of node id's, starting with id1 and ending with id2. |
| 789 | Raises an IndexError between nodes on unconnected graphs. |
| 790 | """ |
| 791 | # Based on: Connelly Barnes, http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/119466 |
| 792 | def flatten(list): |
| 793 | # Flattens a linked list of the form [0,[1,[2,[]]]] |
| 794 | while len(list) > 0: |
| 795 | yield list[0]; list=list[1] |
| 796 | G = adjacency(graph, directed=directed, heuristic=heuristic) |
| 797 | q = [(0, id1, ())] # Heap of (cost, path_head, path_rest). |
| 798 | visited = set() # Visited nodes. |
| 799 | while True: |
| 800 | (cost1, n1, path) = heappop(q) |
| 801 | if n1 not in visited: |
| 802 | visited.add(n1) |
| 803 | if n1 == id2: |
| 804 | return list(flatten(path))[::-1] + [n1] |
| 805 | path = (n1, path) |
| 806 | for (n2, cost2) in G[n1].iteritems(): |
| 807 | if n2 not in visited: |
| 808 | heappush(q, (cost1 + cost2, n2, path)) |
| 809 | |
| 810 | def dijkstra_shortest_paths(graph, id, heuristic=None, directed=False): |
| 811 | """ Dijkstra algorithm for finding the shortest paths from the given node to all other nodes. |
no test coverage detected
searching dependent graphs…