Return the cost of the shortest path between vertices start and end. >>> dijkstra(G, "E", "C") 6 >>> dijkstra(G2, "E", "F") 3 >>> dijkstra(G3, "E", "F") 3
(graph, start, end)
| 35 | |
| 36 | |
| 37 | def dijkstra(graph, start, end): |
| 38 | """Return the cost of the shortest path between vertices start and end. |
| 39 | |
| 40 | >>> dijkstra(G, "E", "C") |
| 41 | 6 |
| 42 | >>> dijkstra(G2, "E", "F") |
| 43 | 3 |
| 44 | >>> dijkstra(G3, "E", "F") |
| 45 | 3 |
| 46 | """ |
| 47 | |
| 48 | heap = [(0, start)] # cost from start node,end node |
| 49 | visited = set() |
| 50 | while heap: |
| 51 | (cost, u) = heapq.heappop(heap) |
| 52 | if u in visited: |
| 53 | continue |
| 54 | visited.add(u) |
| 55 | if u == end: |
| 56 | return cost |
| 57 | for v, c in graph[u]: |
| 58 | if v in visited: |
| 59 | continue |
| 60 | next_item = cost + c |
| 61 | heapq.heappush(heap, (next_item, v)) |
| 62 | return -1 |
| 63 | |
| 64 | |
| 65 | G = { |