Deviopath › Python

Dijkstra Shortest Distances

Hard · Algorithms

Dijkstra's algorithm finds the shortest distance from a start node to every other node when edge weights are non-negative. Keep a min-heap of (distance, node). Pop the closest node; if you already have a shorter distance for it, skip it. Otherwise try every outgoing edge and push any neighbour whose distance improves.

heapq.heappush and heapq.heappop keep a plain list ordered as a min-heap.

Write shortest_distances(edges, start). Each edge is [from, to, weight] and is one-way (directed). Node names are strings and weights are non-negative integers. Return a dict that maps every node reachable from start (including start itself, at 0) to its shortest distance. Leave unreachable nodes out.

Next: Count N-Queens Solutions