{"id":333,"date":"2025-06-21T18:03:58","date_gmt":"2025-06-21T12:33:58","guid":{"rendered":"https:\/\/codeanddebug.in\/blog\/?p=333"},"modified":"2025-06-21T18:07:08","modified_gmt":"2025-06-21T12:37:08","slug":"dijkstra-algorithm-in-python-using-a-set","status":"publish","type":"post","link":"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/","title":{"rendered":"Dijkstra\u2019s Algorithm in Python Using a Set"},"content":{"rendered":"\n<p>See how to run Dijkstra with a <code>set<\/code> 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- &amp; space-complexity.<\/p>\n\n\n\n<p>Here&#8217;s the [<strong><a href=\"https:\/\/www.geeksforgeeks.org\/problems\/implementing-dijkstra-set-1-adjacency-matrix\/1\" target=\"_blank\" rel=\"noreferrer noopener\"><mark style=\"background-color:rgba(0, 0, 0, 0)\" class=\"has-inline-color has-vivid-purple-color\"><span style=\"text-decoration: underline;\">Problem Link<\/span><\/mark><\/a><\/strong>] to begin with.<\/p>\n\n\n<div style=\"max-width: -moz-fit-content; \" class=\"wp-block-ub-table-of-contents-block ub_table-of-contents ub_table-of-contents-collapsed\" id=\"ub_table-of-contents-920055fa-01ad-4afc-8bd3-79f33ef85b35\" data-linktodivider=\"false\" data-showtext=\"show\" data-hidetext=\"hide\" data-scrolltype=\"auto\" data-enablesmoothscroll=\"true\" data-initiallyhideonmobile=\"false\" data-initiallyshow=\"false\"><div class=\"ub_table-of-contents-header-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-header\" style=\"text-align: left; \">\n\t\t\t\t<div class=\"ub_table-of-contents-title\">Contents:<\/div>\n\t\t\t\t<div class=\"ub_table-of-contents-header-toggle\">\n\t\t\t<div class=\"ub_table-of-contents-toggle\" style=\"\">\n\t\t\t\u00a0[<a class=\"ub_table-of-contents-toggle-link\" href=\"#\" style=\"\">show<\/a>]\n\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t<\/div>\n\t\t<\/div><div class=\"ub_table-of-contents-extra-container\" style=\"\">\n\t\t\t<div class=\"ub_table-of-contents-container ub_table-of-contents-1-column ub-hide\">\n\t\t\t\t<ul style=\"\"><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#0-1-what-does-the-problem-ask\" style=\"\">1. What does the problem ask?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#1-2-quick-examples\" style=\"\">2. Quick examples<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#2-3-intuition-amp-approach\" style=\"\">3. Intuition &amp; approach<\/a><ul><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#3-31-classic-dijkstra-idea\" style=\"\">3.1 Classic Dijkstra idea<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#4-32-why-use-a-set-\" style=\"\">3.2 Why use a set?<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#5-33-algorithm-steps-with-a-set\" style=\"\">3.3 Algorithm steps with a set<\/a><\/li><\/ul><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#6-4-code\" style=\"\">4. Code<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#7-5%E2%80%82step-by-step-code-explanation\" style=\"\">5\u2002Step-by-step code explanation<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#8-6-dry-run-on-a-small-graph\" style=\"\">6. Dry run on a small graph<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#9-7-complexity\" style=\"\">7. Complexity<\/a><\/li><li style=\"\"><a href=\"https:\/\/codeanddebug.in\/blog\/dijkstra-algorithm-in-python-using-a-set\/#10-8-conclusion\" style=\"\">8. Conclusion<\/a><\/li><\/ul>\n\t\t\t<\/div>\n\t\t<\/div><\/div>\n\n\n<h2 class=\"wp-block-heading\" id=\"0-1-what-does-the-problem-ask\">1. What does the problem ask?<\/h2>\n\n\n\n<blockquote class=\"wp-block-quote is-layout-flow wp-block-quote-is-layout-flow\">\n<p>For a directed graph with non-negative edge weights, return an array<br><code>dist<\/code> where <code>dist[i]<\/code> is the length of the shortest path from a given<br>source <code>src<\/code> to vertex <code>i<\/code>.<\/p>\n<\/blockquote>\n\n\n\n<p>If a vertex cannot be reached, its distance stays at \u201cinfinity\u201d<br>(in code we use <code>sys.maxsize<\/code>).<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"1-2-quick-examples\">2. Quick examples<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th><code>V<\/code><\/th><th><code>edges [u,v,w]<\/code><\/th><th><code>src<\/code><\/th><th>Output <code>dist<\/code> (shortest paths)<\/th><\/tr><\/thead><tbody><tr><td>4<\/td><td><code>[[0,1,1],[0,2,4],[1,2,2],[1,3,5],[2,3,1]]<\/code><\/td><td>0<\/td><td><code>[0, 1, 3, 4]<\/code><\/td><\/tr><tr><td>3<\/td><td><code>[[0,1,7],[1,2,3]]<\/code><\/td><td>2<\/td><td><code>[\u221e, \u221e, 0]<\/code> (here <code>\u221e<\/code> stays <code>sys.maxsize<\/code>)<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"2-3-intuition-amp-approach\">3. Intuition &amp; approach<\/h2>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"3-31-classic-dijkstra-idea\">3.1 Classic Dijkstra idea<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Distance array<\/strong> holds our best\u2010so\u2010far cost for each vertex.<\/li>\n\n\n\n<li>We repeatedly <strong>pick the not-yet-processed vertex<\/strong> with the smallest tentative distance.<\/li>\n\n\n\n<li>For each outgoing edge <code>(u \u2192 v, w)<\/code>, we try to shorten <code>dist[v]<\/code> via <code>u<\/code>.<br>This step is called <strong>relaxation<\/strong>.<\/li>\n<\/ol>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"4-32-why-use-a-set-\">3.2 Why use a <code>set<\/code>?<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>In C++ the typical container is a balanced BST (<code>std::set<\/code>).<\/li>\n\n\n\n<li>In Python a normal <code>set<\/code> is <strong>unordered<\/strong>, so to find the minimum we still call <code>min(my_set)<\/code> each time \u2013 this costs <code>O(k)<\/code> where <code>k<\/code> is set size.<\/li>\n\n\n\n<li>That makes this version <strong>slower<\/strong> than the min-heap (<code>heapq<\/code>) one, but the algorithmic idea is identical and still correct.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"5-33-algorithm-steps-with-a-set\">3.3 Algorithm steps with a set<\/h3>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Build<\/strong> an adjacency list from the edge list.<\/li>\n\n\n\n<li>Fill <code>distance<\/code> with <code>\u221e<\/code>, set <code>distance[src] = 0<\/code>.<\/li>\n\n\n\n<li>Insert <code>(0, src)<\/code> into <code>my_set<\/code>. Each pair is <code>(currentDistance, vertex)<\/code>.<\/li>\n\n\n\n<li>While the set is not empty\n<ol class=\"wp-block-list\">\n<li>Pull out the <strong>pair with the smallest distance<\/strong> using <code>min()<\/code>.<\/li>\n\n\n\n<li>For every neighbour <code>(v, weight)<\/code> of that vertex, try to relax:\n<ul class=\"wp-block-list\">\n<li>If <code>dist[u] + weight &lt; dist[v]<\/code>,\n<ul class=\"wp-block-list\">\n<li>Remove the old pair for <code>v<\/code> (if present),<\/li>\n\n\n\n<li>Update <code>dist[v]<\/code>,<\/li>\n\n\n\n<li>Insert the new pair <code>(dist[v], v)<\/code>.<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n<\/li>\n\n\n\n<li>When the set empties, <code>distance<\/code> contains final shortest paths.<\/li>\n<\/ol>\n\n\n\n<p>Because the set always holds the smallest distance seen so far for every <em>processed<\/em> vertex, we never miss the globally smallest tentative distance.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"6-4-code\">4. Code<\/h2>\n\n\n\n<div class=\"wp-block-kevinbatdorf-code-block-pro\" data-code-block-pro-font-family=\"Code-Pro-JetBrains-Mono\" style=\"font-size:.875rem;font-family:Code-Pro-JetBrains-Mono,ui-monospace,SFMono-Regular,Menlo,Monaco,Consolas,monospace;line-height:1.25rem;--cbp-tab-width:2;tab-size:var(--cbp-tab-width, 2)\"><span style=\"display:block;padding:16px 0 0 16px;margin-bottom:-1px;width:100%;text-align:left;background-color:#1E1E1E\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"54\" height=\"14\" viewBox=\"0 0 54 14\"><g fill=\"none\" fill-rule=\"evenodd\" transform=\"translate(1 1)\"><circle cx=\"6\" cy=\"6\" r=\"6\" fill=\"#FF5F56\" stroke=\"#E0443E\" stroke-width=\".5\"><\/circle><circle cx=\"26\" cy=\"6\" r=\"6\" fill=\"#FFBD2E\" stroke=\"#DEA123\" stroke-width=\".5\"><\/circle><circle cx=\"46\" cy=\"6\" r=\"6\" fill=\"#27C93F\" stroke=\"#1AAB29\" stroke-width=\".5\"><\/circle><\/g><\/svg><\/span><span role=\"button\" tabindex=\"0\" data-code=\"import sys\n\nclass Solution:\n    # Returns shortest distances from src to all other vertices\n    def dijkstra(self, V, edges, src):\n        # ------- 1. Build adjacency list -------\n        adj_list = [[] for _ in range(V)]\n        for u, v, d in edges:\n            adj_list[u].append([v, d])\n\n        # ------- 2. Distance array &amp; set -------\n        distance = [sys.maxsize for _ in range(V)]\n        distance[src] = 0\n\n        my_set = set()\n        my_set.add((0, src))                       # (dist, node)\n\n        # ------- 3. Main loop -------\n        while len(my_set) != 0:\n            dist, node = min(my_set)               # slow O(k) min()\n            my_set.discard((dist, node))           # remove picked pair\n\n            for adjNode, weight in adj_list[node]:\n                dist_trav = dist + weight          # path through 'node'\n                if dist_trav &lt; distance[adjNode]:  # found a better path\n                    if distance[adjNode] != sys.maxsize:\n                        my_set.discard((distance[adjNode], adjNode))\n                    distance[adjNode] = dist_trav\n                    my_set.add((dist_trav, adjNode))\n\n        return distance\" style=\"color:#D4D4D4;display:none\" aria-label=\"Copy\" class=\"code-block-pro-copy-button\"><svg xmlns=\"http:\/\/www.w3.org\/2000\/svg\" style=\"width:24px;height:24px\" fill=\"none\" viewBox=\"0 0 24 24\" stroke=\"currentColor\" stroke-width=\"2\"><path class=\"with-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2m-6 9l2 2 4-4\"><\/path><path class=\"without-check\" stroke-linecap=\"round\" stroke-linejoin=\"round\" d=\"M9 5H7a2 2 0 00-2 2v12a2 2 0 002 2h10a2 2 0 002-2V7a2 2 0 00-2-2h-2M9 5a2 2 0 002 2h2a2 2 0 002-2M9 5a2 2 0 012-2h2a2 2 0 012 2\"><\/path><\/svg><\/span><pre class=\"shiki dark-plus\" style=\"background-color: #1E1E1E\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color: #C586C0\">import<\/span><span style=\"color: #D4D4D4\"> sys<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #569CD6\">class<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #4EC9B0\">Solution<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #6A9955\"># Returns shortest distances from src to all other vertices<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">    <\/span><span style=\"color: #569CD6\">def<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">dijkstra<\/span><span style=\"color: #D4D4D4\">(<\/span><span style=\"color: #9CDCFE\">self<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">V<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">edges<\/span><span style=\"color: #D4D4D4\">, <\/span><span style=\"color: #9CDCFE\">src<\/span><span style=\"color: #D4D4D4\">):<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># ------- 1. Build adjacency list -------<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        adj_list = [[] <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(V)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> u, v, d <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> edges:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            adj_list[u].append([v, d])<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># ------- 2. Distance array &amp; set -------<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        distance = [sys.maxsize <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> _ <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">range<\/span><span style=\"color: #D4D4D4\">(V)]<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        distance[src] = <\/span><span style=\"color: #B5CEA8\">0<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        my_set = <\/span><span style=\"color: #4EC9B0\">set<\/span><span style=\"color: #D4D4D4\">()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        my_set.add((<\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">, src))                       <\/span><span style=\"color: #6A9955\"># (dist, node)<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #6A9955\"># ------- 3. Main loop -------<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">while<\/span><span style=\"color: #D4D4D4\"> <\/span><span style=\"color: #DCDCAA\">len<\/span><span style=\"color: #D4D4D4\">(my_set) != <\/span><span style=\"color: #B5CEA8\">0<\/span><span style=\"color: #D4D4D4\">:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            dist, node = <\/span><span style=\"color: #DCDCAA\">min<\/span><span style=\"color: #D4D4D4\">(my_set)               <\/span><span style=\"color: #6A9955\"># slow O(k) min()<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            my_set.discard((dist, node))           <\/span><span style=\"color: #6A9955\"># remove picked pair<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">            <\/span><span style=\"color: #C586C0\">for<\/span><span style=\"color: #D4D4D4\"> adjNode, weight <\/span><span style=\"color: #C586C0\">in<\/span><span style=\"color: #D4D4D4\"> adj_list[node]:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                dist_trav = dist + weight          <\/span><span style=\"color: #6A9955\"># path through &#39;node&#39;<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> dist_trav &lt; distance[adjNode]:  <\/span><span style=\"color: #6A9955\"># found a better path<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    <\/span><span style=\"color: #C586C0\">if<\/span><span style=\"color: #D4D4D4\"> distance[adjNode] != sys.maxsize:<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                        my_set.discard((distance[adjNode], adjNode))<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    distance[adjNode] = dist_trav<\/span><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">                    my_set.add((dist_trav, adjNode))<\/span><\/span>\n<span class=\"line\"><\/span>\n<span class=\"line\"><span style=\"color: #D4D4D4\">        <\/span><span style=\"color: #C586C0\">return<\/span><span style=\"color: #D4D4D4\"> distance<\/span><\/span><\/code><\/pre><\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"7-5%E2%80%82step-by-step-code-explanation\">5\u2002Step-by-step code explanation<\/h2>\n\n\n\n<ol class=\"wp-block-list\">\n<li><strong>Adjacency list<\/strong><br><code>adj_list[u]<\/code> stores <code>[v, weight]<\/code> pairs \u2013 quick to iterate.<\/li>\n\n\n\n<li><strong>Initialization<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>distance[src] = 0<\/code>; all others <code>\u221e<\/code>.<\/li>\n\n\n\n<li><code>my_set<\/code> starts with just <code>(0, src)<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Picking the next vertex<\/strong>\n<ul class=\"wp-block-list\">\n<li><code>min(my_set)<\/code> scans the set to find the pair with the smallest <code>dist<\/code>.<\/li>\n\n\n\n<li>That vertex\u2019s distance is now <em>final<\/em>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Relaxation<\/strong>\n<ul class=\"wp-block-list\">\n<li>Compute <code>dist_trav = dist + weight<\/code>.<\/li>\n\n\n\n<li>If it beats <code>distance[adjNode]<\/code>, update it.<\/li>\n\n\n\n<li>Because <code>my_set<\/code> might already store an older (bigger) pair for <code>adjNode<\/code>, we delete that pair before inserting the new one.<\/li>\n<\/ul>\n<\/li>\n\n\n\n<li><strong>Loop ends<\/strong> when <code>my_set<\/code> is empty, no vertex left to improve.<\/li>\n<\/ol>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"8-6-dry-run-on-a-small-graph\">6. Dry run on a small graph<\/h2>\n\n\n\n<p>Graph: <code>0 \u2192 1 (4)<\/code>, <code>0 \u2192 2 (1)<\/code>, <code>2 \u2192 1 (2)<\/code><\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th><code>my_set<\/code> (before pick)<\/th><th>Pick <code>(dist,node)<\/code><\/th><th>Relaxations<\/th><th><code>distance<\/code> after step<\/th><\/tr><\/thead><tbody><tr><td><code>{(0,0)}<\/code><\/td><td><code>(0,0)<\/code><\/td><td>update <code>1\u21924<\/code>, <code>2\u21921<\/code><\/td><td><code>[0,4,1]<\/code><\/td><\/tr><tr><td><code>{(1,2),(4,1)}<\/code><\/td><td><code>(1,2)<\/code><\/td><td>path to <code>1<\/code> improves: remove <code>(4,1)<\/code>, add <code>(3,1)<\/code><\/td><td><code>[0,3,1]<\/code><\/td><\/tr><tr><td><code>{(3,1)}<\/code><\/td><td><code>(3,1)<\/code><\/td><td>no neighbours better<\/td><td><code>[0,3,1]<\/code><\/td><\/tr><tr><td><code>\u2205<\/code><\/td><td>loop ends<\/td><td>\u2013<\/td><td>final result<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"9-7-complexity\">7. Complexity<\/h2>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><thead><tr><th>Measure<\/th><th>Big-O<\/th><th>Plain words<\/th><\/tr><\/thead><tbody><tr><td><strong>Time<\/strong><\/td><td><strong>O(V\u00b2)<\/strong> worst-case<\/td><td>Each <code>min(my_set)<\/code> is <code>O(V)<\/code>, done up to <code>V<\/code> times; relaxing edges adds up to <code>O(E)<\/code>, but <code>V\u00b2<\/code> dominates for dense graphs.<\/td><\/tr><tr><td><strong>Space<\/strong><\/td><td><strong>O(V + E)<\/strong><\/td><td>Adjacency list plus set plus distance array<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>Compared to the <strong>heap<\/strong> version (<code>O((V+E) log V)<\/code>), this set approach is <strong>slower for large graphs<\/strong>, especially when <code>V<\/code> is big.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"10-8-conclusion\">8. Conclusion<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Using a <strong>set<\/strong> makes Dijkstra easy to code but not the fastest in Python because finding the minimum is linear in the set size.<\/li>\n\n\n\n<li>Still, the algorithmic steps\u2014pick the lightest vertex, relax its edges, repeat, stay exactly the same.<\/li>\n\n\n\n<li>For interviews or real projects in Python, prefer the <strong>priority-queue (<code>heapq<\/code>)<\/strong> version, but knowing this set variant helps you understand the inner workings and the importance of having an efficient \u201cfind-min\u201d structure.<\/li>\n<\/ul>\n\n\n\n<div class=\"wp-block-buttons is-content-justification-center is-layout-flex wp-container-core-buttons-is-layout-16018d1d wp-block-buttons-is-layout-flex\">\n<div class=\"wp-block-button\"><a class=\"wp-block-button__link wp-element-button\" href=\"https:\/\/www.codeanddebug.in\/course\/zero-to-hero-python-dsa\">Join our Advance DSA COURSE<\/a><\/div>\n<\/div>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<p><em>For any changes to the article, kindly email at <a href=\"mailto:code@codeanddebug.in\">code@codeanddebug.in<\/a> or contact us at <a href=\"tel:+91-9712928220\">+91-9712928220<\/a>.<\/em><\/p>\n","protected":false},"excerpt":{"rendered":"<p>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- &amp; space-complexity. Here&#8217;s the [Problem Link] to begin with. 1. What does the problem ask? For a directed graph<\/p>\n","protected":false},"author":1,"featured_media":334,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[24,17,19],"class_list":{"0":"post-333","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-data-structures-and-algorithm","8":"category-intermediate","9":"tag-dijkstra-algorithm","10":"tag-graph","11":"tag-medium"},"featured_image_src":"https:\/\/codeanddebug.in\/blog\/wp-content\/uploads\/2025\/06\/dijkstra-algorithm-using-set-featured-image.png","author_info":{"display_name":"codeanddebug","author_link":"https:\/\/codeanddebug.in\/blog\/author\/codeanddebug\/"},"_links":{"self":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/333","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/comments?post=333"}],"version-history":[{"count":3,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/333\/revisions"}],"predecessor-version":[{"id":370,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/posts\/333\/revisions\/370"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media\/334"}],"wp:attachment":[{"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/media?parent=333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/categories?post=333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/codeanddebug.in\/blog\/wp-json\/wp\/v2\/tags?post=333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}