BeginnerCoder
DonateLesson 22 — Dijkstra (expert)
Dijkstra: cheapest paths in a weighted graph
A graph is a set of nodes (places) joined by edges (roads); a weight is an edge's cost. Dijkstra's algorithm finds the cheapest cost from a start to every node. It always expands the cheapest node found so far, using a priority queue (heapq pops the smallest item). Then it relaxes each edge: if going through u makes v cheaper, record it.
new_cost = cost + edge
if new_cost < best.get(city, float("inf")):
best[city] = new_cost
heapq.heappush(queue, (new_cost, city))
Why it matters: this is how map apps and network routers find the fastest route.
Write the relax step for each edge. A→C costs 3 via B, cheaper than the direct 4.
Run your code — when the output matches the task, you will see a green check. Then mark the lesson complete.
Test your knowledgeA quick 3-question quiz on this lesson — instant feedback.
Ready for more? Optional paid resources that pick up where this lesson leaves off.
Some links on this page are affiliate links: we may earn a commission at no extra cost to you. As an Amazon Associate I earn from qualifying purchases.
Project-based Algorithms Foundations courses if you want a structured paid path after the free lessons. Wait for a sale — prices drop often.
Browse on Udemy →Search Amazon for Algorithms Foundations books — check the publication year so the examples match current versions.
Search Amazon →