See how to run Dijkstra with a set
instead of a heap. We break down the idea, walk through clear Python code (unchanged lines, only comments added), give easy examples, a dry run, and precise time- & space-complexity.
Here’s the [Problem Link] to begin with.
1. What does the problem ask?
For a directed graph with non-negative edge weights, return an array
dist
wheredist[i]
is the length of the shortest path from a given
sourcesrc
to vertexi
.
If a vertex cannot be reached, its distance stays at “infinity”
(in code we use sys.maxsize
).
2. Quick examples
V | edges [u,v,w] | src | Output dist (shortest paths) |
---|---|---|---|
4 | [[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,1]] | 0 | [0, 1, 3, 4] |
3 | [[0,1,7],[1,2,3]] | 2 | [∞, ∞, 0] (here ∞ stays sys.maxsize ) |
3. Intuition & approach
3.1 Classic Dijkstra idea
- Distance array holds our best‐so‐far cost for each vertex.
- We repeatedly pick the not-yet-processed vertex with the smallest tentative distance.
- For each outgoing edge
(u → v, w)
, we try to shortendist[v]
viau
.
This step is called relaxation.
3.2 Why use a set
?
- In C++ the typical container is a balanced BST (
std::set
). - In Python a normal
set
is unordered, so to find the minimum we still callmin(my_set)
each time – this costsO(k)
wherek
is set size. - That makes this version slower than the min-heap (
heapq
) one, but the algorithmic idea is identical and still correct.
3.3 Algorithm steps with a set
- Build an adjacency list from the edge list.
- Fill
distance
with∞
, setdistance[src] = 0
. - Insert
(0, src)
intomy_set
. Each pair is(currentDistance, vertex)
. - While the set is not empty
- Pull out the pair with the smallest distance using
min()
. - For every neighbour
(v, weight)
of that vertex, try to relax:- If
dist[u] + weight < dist[v]
,- Remove the old pair for
v
(if present), - Update
dist[v]
, - Insert the new pair
(dist[v], v)
.
- Remove the old pair for
- If
- Pull out the pair with the smallest distance using
- When the set empties,
distance
contains final shortest paths.
Because the set always holds the smallest distance seen so far for every processed vertex, we never miss the globally smallest tentative distance.
4. Code
import sys
class Solution:
# Returns shortest distances from src to all other vertices
def dijkstra(self, V, edges, src):
# ------- 1. Build adjacency list -------
adj_list = [[] for _ in range(V)]
for u, v, d in edges:
adj_list[u].append([v, d])
# ------- 2. Distance array & set -------
distance = [sys.maxsize for _ in range(V)]
distance[src] = 0
my_set = set()
my_set.add((0, src)) # (dist, node)
# ------- 3. Main loop -------
while len(my_set) != 0:
dist, node = min(my_set) # slow O(k) min()
my_set.discard((dist, node)) # remove picked pair
for adjNode, weight in adj_list[node]:
dist_trav = dist + weight # path through 'node'
if dist_trav < distance[adjNode]: # found a better path
if distance[adjNode] != sys.maxsize:
my_set.discard((distance[adjNode], adjNode))
distance[adjNode] = dist_trav
my_set.add((dist_trav, adjNode))
return distance
5 Step-by-step code explanation
- Adjacency list
adj_list[u]
stores[v, weight]
pairs – quick to iterate. - Initialization
distance[src] = 0
; all others∞
.my_set
starts with just(0, src)
.
- Picking the next vertex
min(my_set)
scans the set to find the pair with the smallestdist
.- That vertex’s distance is now final.
- Relaxation
- Compute
dist_trav = dist + weight
. - If it beats
distance[adjNode]
, update it. - Because
my_set
might already store an older (bigger) pair foradjNode
, we delete that pair before inserting the new one.
- Compute
- Loop ends when
my_set
is empty, no vertex left to improve.
6. Dry run on a small graph
Graph: 0 → 1 (4)
, 0 → 2 (1)
, 2 → 1 (2)
my_set (before pick) | Pick (dist,node) | Relaxations | distance after step |
---|---|---|---|
{(0,0)} | (0,0) | update 1→4 , 2→1 | [0,4,1] |
{(1,2),(4,1)} | (1,2) | path to 1 improves: remove (4,1) , add (3,1) | [0,3,1] |
{(3,1)} | (3,1) | no neighbours better | [0,3,1] |
∅ | loop ends | – | final result |
7. Complexity
Measure | Big-O | Plain words |
---|---|---|
Time | O(V²) worst-case | Each min(my_set) is O(V) , done up to V times; relaxing edges adds up to O(E) , but V² dominates for dense graphs. |
Space | O(V + E) | Adjacency list plus set plus distance array |
Compared to the heap version (O((V+E) log V)
), this set approach is slower for large graphs, especially when V
is big.
8. Conclusion
- Using a set makes Dijkstra easy to code but not the fastest in Python because finding the minimum is linear in the set size.
- Still, the algorithmic steps—pick the lightest vertex, relax its edges, repeat, stay exactly the same.
- For interviews or real projects in Python, prefer the priority-queue (
heapq
) version, but knowing this set variant helps you understand the inner workings and the importance of having an efficient “find-min” structure.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.