Dijkstra's Shortest Path

DSA · Graphs

Theory

Dijkstra's algorithm finds the shortest distance from a source to every vertex in a graph with non-negative edge weights. It keeps tentative distances, repeatedly picks the unvisited vertex with the smallest distance (using a priority queue), and relaxes its edges: if going through this vertex gives a shorter path to a neighbour, the neighbour's distance is updated. With a binary heap it runs in O((V + E) log V).

Why we use it

It is the standard algorithm for road navigation, network routing and any weighted shortest-path problem without negative weights.

When to use it

Use it for maps and GPS, network latency routing, cheapest flights, and game path costs. Do not use it with negative weights; use Bellman-Ford instead.

How it works

  1. dist[source] = 0, others infinity; heap = [(0, source)]
  2. Heap empty? Yes: Done. No: Pop node u with smallest distance.
  3. For each edge u -> v with weight w
  4. dist[u] + w < dist[v]? Yes: Update dist[v], push (dist[v], v). No: Skip.
  5. dist holds shortest distances (non-negative weights)

Syntax

dist[source] = 0, others = infinity
while unvisited remain:
    u = unvisited vertex with smallest dist
    for v, w in graph[u]:
        if dist[u] + w < dist[v]: dist[v] = dist[u] + w

Time: O((V+E) log V) with a heap

Example

graph = {
    "Home": [("Mall", 4), ("Office", 1)],
    "Office": [("Mall", 2), ("Gym", 5)],
    "Mall": [("Gym", 1)],
    "Gym": [],
}

def dijkstra(src):
    dist = {v: float("inf") for v in graph}
    prev = {}
    dist[src] = 0
    unvisited = set(graph)
    while unvisited:
        u = min(unvisited, key=lambda v: dist[v])
        unvisited.remove(u)
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u
    return dist, prev

dist, prev = dijkstra("Home")
print("Distances:", dist)
path, node = [], "Gym"
while node != "Home":
    path.append(node); node = prev[node]
print("Best route:", " -> ".join(["Home"] + path[::-1]))

Key points

DSA topics

Introduction to DSA

Arrays and Searching

Sorting Algorithms

Linked Lists

Stacks and Queues

Hashing

Trees

Heaps

Graphs

Algorithm Techniques

Classic Algorithms

Dynamic Programming

T
Tech Town
Log InSign Up Free
Home SQL Python DSA Power BI Snowflake Databricks Spark Gen AI Practice Problems Contest Blog

Data Structures & Algorithms

The complete DSA roadmap: theory, why and when to use every structure and algorithm, Big O complexity, and Python code you can run right here in the browser.

{{ sectionCount }}
Sections
{{ topicCount }}
Topics
Free
Forever
Hands-on practice Practice DSA Online 251 problems across 13 patterns, with hidden tests and step-by-step optimal solutions. Start practising →
Section {{ sec.num }}

{{ sec.label }}

DSA  /  {{ current.sectionLabel }}  /  {{ current.name }}

{{ current.name }}

Theory

{{ current.def }}

Why we use it

{{ current.why }}

When to use it

{{ current.when }}

Flowchart — how {{ current.name }} works
{{ nd.text }}
{{ nd.text }}
◇ {{ nd.text }}
Yes → {{ nd.yes }}
No → {{ nd.no }}
Step-by-step visualisation
{{ cell.v }}
{{ cell.i }} {{ cell.tag }}
Step {{ vizStepLabel }}: {{ vizNote }}
■ comparing ■ swapping / moving ■ done / found ■ out of range
Complexity & Pseudocode
{{ current.syntax }}
Example Code
{{ current.example }}
▶ Try It Live — runs real Python 3 in your browser (first run loads the engine)
{{ liveOutput }}
{{ liveError }}
Key Points — click to check off as you learn
  • {{ pt.mark }} {{ pt.text }}

Share this topic