AdvancedChallenge 33 of 34

Dijkstra's shortest path

Write shortest_path(graph, start, end) for a weighted graph given as {node: {neighbour: weight}}. Return (distance, path) with the path as a of nodes, or (, []) if end is unreachable. Use heapq for the priority .

Examples

shortest_path({"A": {"B": 1, "C": 4}, "B": {"C": 2, "D": 5}, "C": {"D": 1}, "D": {}}, "A", "D") → (4, ["A", "B", "C", "D"])

Exercise

Dijkstra's shortest path

5 checks

import heapq


def shortest_path(graph, start, end):
    ...


g = {"A": {"B": 1, "C": 4}, "B": {"C": 2, "D": 5}, "C": {"D": 1}, "D": {}}
print(shortest_path(g, "A", "D"))

Output

Press Run to try your code, then Check answer to grade it.