Close Menu
    Code and Debug
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook X (Twitter) Instagram YouTube WhatsApp
    • Home
    • Our Courses
    • Blog
    • About Us
    • Contact Us
    Facebook Instagram YouTube LinkedIn WhatsApp
    Code and Debug – BlogCode and Debug – Blog
    Code and Debug – BlogCode and Debug – Blog
    Home»Data Structures & Algorithms»Dijkstra’s Algorithm in Python Using a Set
    Data Structures & Algorithms

    Dijkstra’s Algorithm in Python Using a Set

    codeanddebugBy codeanddebug21 June 2025Updated:21 June 2025No Comments4 Mins Read
    Share Facebook Twitter Pinterest LinkedIn Tumblr Reddit Telegram Email
    Featured image of question to implement dijkstra algorithm
    Share
    Facebook Twitter LinkedIn Pinterest Email

    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.

    Contents:
     [show]
    • 1. What does the problem ask?
    • 2. Quick examples
    • 3. Intuition & approach
      • 3.1 Classic Dijkstra idea
      • 3.2 Why use a set?
      • 3.3 Algorithm steps with a set
    • 4. Code
    • 5 Step-by-step code explanation
    • 6. Dry run on a small graph
    • 7. Complexity
    • 8. Conclusion

    1. What does the problem ask?

    For a directed graph with non-negative edge weights, return an array
    dist where dist[i] is the length of the shortest path from a given
    source src to vertex i.

    If a vertex cannot be reached, its distance stays at “infinity”
    (in code we use sys.maxsize).


    2. Quick examples

    Vedges [u,v,w]srcOutput 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

    1. Distance array holds our best‐so‐far cost for each vertex.
    2. We repeatedly pick the not-yet-processed vertex with the smallest tentative distance.
    3. For each outgoing edge (u → v, w), we try to shorten dist[v] via u.
      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 call min(my_set) each time – this costs O(k) where k 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

    1. Build an adjacency list from the edge list.
    2. Fill distance with ∞, set distance[src] = 0.
    3. Insert (0, src) into my_set. Each pair is (currentDistance, vertex).
    4. While the set is not empty
      1. Pull out the pair with the smallest distance using min().
      2. 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).
    5. 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

    1. Adjacency list
      adj_list[u] stores [v, weight] pairs – quick to iterate.
    2. Initialization
      • distance[src] = 0; all others ∞.
      • my_set starts with just (0, src).
    3. Picking the next vertex
      • min(my_set) scans the set to find the pair with the smallest dist.
      • That vertex’s distance is now final.
    4. Relaxation
      • Compute dist_trav = dist + weight.
      • If it beats distance[adjNode], update it.
      • Because my_set might already store an older (bigger) pair for adjNode, we delete that pair before inserting the new one.
    5. 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)Relaxationsdistance 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

    MeasureBig-OPlain words
    TimeO(V²) worst-caseEach min(my_set) is O(V), done up to V times; relaxing edges adds up to O(E), but V² dominates for dense graphs.
    SpaceO(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.
    Join our Advance DSA COURSE

    For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.

    Dijkstra Algorithm Graph Medium
    Share. Facebook Twitter Pinterest LinkedIn Tumblr Email
    Previous ArticleDijkstra’s Algorithm with a Priority Queue
    Next Article Printing the Actual Shortest Path with Dijkstra Algorithm
    codeanddebug
    • Website

    Related Posts

    Data Structures & Algorithms

    Median of Two Sorted Arrays | Leetcode 4 | Optimal Binary Search Solution

    10 July 2025
    Data Structures & Algorithms

    Minimize Max Distance to Gas Station | GFG Practice | Optimal Binary Search

    10 July 2025
    Data Structures & Algorithms

    The Painter’s Partition Problem-II | GeeksforGeeks Solution Explained

    10 July 2025
    Add A Comment
    Leave A Reply Cancel Reply

    Categories
    • Data Structures & Algorithms (115)
      • Beginner (46)
      • Expert (34)
      • Intermediate (35)
    • Uncategorised (1)
    Recent Posts

    Median of Two Sorted Arrays | Leetcode 4 | Optimal Binary Search Solution

    10 July 2025

    Minimize Max Distance to Gas Station | GFG Practice | Optimal Binary Search

    10 July 2025

    The Painter’s Partition Problem-II | GeeksforGeeks Solution Explained

    10 July 2025

    Allocate Minimum Pages | GFG | Binary Search

    10 July 2025

    Aggressive Cows | GeeksforGeeks Solution Explained | Binary Search

    10 July 2025
    Facebook Instagram YouTube LinkedIn WhatsApp
    © 2025 Code and Debug. All rights reserved.

    Type above and press Enter to search. Press Esc to cancel.