Sign in
Skip to solution
hardDSA

How does Dijkstra's algorithm work?

223 views
01

Understand the problem

Explain shortest paths.

graphsshortest-path
02

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Dijkstra's finds shortest paths from a source in a graph with non-negative weights. It repeatedly picks the unvisited node with the smallest known distance (via a min-heap), relaxes its edges, and finalizes it — running in O((V+E) log V). For negative weights, use Bellman-Ford.

Solution ready — 2 min read

Classified // press E to declassify

04

Read the code

Dijkstra with a min-heap
Run Playground
import heapq

def dijkstra(graph, source):
    # graph: {node: [(neighbor, weight), ...]}
    dist = {source: 0}
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist.get(u, float('inf')):
            continue                    # stale entry
        for v, w in graph[u]:
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist


# --- demo ---  nodes A=0 B=1 C=2 D=3
graph = {0: [(1, 4), (2, 1)], 1: [(3, 1)], 2: [(1, 2), (3, 5)], 3: []}
print(dijkstra(graph, 0))   # {0: 0, 2: 1, 1: 3, 3: 4}
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

No responses yet. Be the first to share what you think.

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 123 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track