Dijkstra: Shortest Path

Challenge

Implement dijkstra(graph, start, end). The directed graph is a dictionary mapping string node labels to dictionaries of neighbour labels and non-negative numeric edge weights. Every referenced neighbour is also a key in graph. Return the minimum sum of edge weights from start to end, or the exact string "invalid" if either node is absent or the destination is unreachable. A node has distance 0 from itself. Zero-weight edges and cycles are allowed; negative weights are outside the input contract.

For {"A":{"B":0.2},"B":{"C":0.3},"C":{}}, the distance from A to C is 0.5. Do not round intermediate distances.

Target complexity: O((V + E) log V)

Return values are checked by type. Use the exact function name. Print output is not your answer. Tests have time and memory limits.

Public examples

[{'A': {'B': 0.2}, 'B': {'A': 0.2, 'C': 0.3}, 'C': {'A': 0.5, 'B': 0.3}}, 'A', 'C']

0.5

[{'A': {'B': 1}, 'B': {'A': 1}}, 'A', 'B']

1

The worked solution unlocks after completion, or with Premium access.