DSA — Graph Algorithms

Dijkstra's Algorithm

Find shortest paths from a source to all vertices in a weighted graph with non-negative edge weights.

— min read

O((V+E)log V)

ShortestPath Wt.

Min-HeapPriority Q

Non-negWeights

GreedyApproach

// DIJKSTRA'S ALGORITHM

Interactive visualization

How It Works

Python Code

Complexity

Quiz

Practice

Initialize

dist[source]=0, all others=infinity. Use min-heap.

dist = {v: inf for v in graph}; dist[src] = 0

Greedy Pick

Extract vertex with minimum known distance.

u, d = heappop(heap)

Relax Edges

For each neighbor: if dist[u]+w < dist[v], update.

if dist[u]+w < dist[v]: dist[v]=dist[u]+w

Repeat

Until heap is empty — all reachable nodes finalized.

while heap: ...

python

import heapq

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

O((V+E) log V)

With Heap

Min-heap + adjacency list

O(V²)

Naive

Simple array, no heap

Non-neg

Weights

Fails with negative edge weights

Bellman-Ford

Negative

Use Bellman-Ford for negative weights

Dijkstra fails when graph has:

Progress 0 / 3 solved

3 problems · 1 PBC · 2 Startup

#105 Dijkstra's Shortest Path Zepto STARTUP →

#106 Bellman-Ford Algorithm Niyo STARTUP →

#140 Network Delay Time Google, Microsoft PBC →

← DFS Traversal Bubble Sort →