Python Dijkstra Shortest Path

Background

Dijkstra algorithm finds shortest paths in non-negative weighted graphs, used in GPS navigation and network routing.

Problem

Write a function that takes a weighted graph (adjacency dict) and a start node, returning shortest distances to all nodes.

Input

A graph as a dict of node -> list of (neighbor, weight) pairs, and a start node.

Output

A dict mapping each node to its shortest distance from the start.

Sample tests

Input: {"A":[("B",1),("C",4)], "B":[("C",2)], "C":[]}, start="A"

Expected: {"A":0,"B":1,"C":3}

Your solution

Learning objective

Learn Dijkstra algorithm, priority queue usage with heapq, and shortest path computation.