<p>I know that this has been debated and discussed millions of times, but I couldn't find anything that explains why the outer while loop in a typical Dijkstra's min-heap implementation is considered  ()  I have created a case where it can reach (V^2)</p>
<p>consider this graph: (sketch it with your hand to see what I'm pointing to)
the first pair describes the edge and third number is the cost</p>
<pre><code>1 2 1
1 3 2
1 4 3
2 5 6
2 6 6
2 7 6
3 5 3
3 6 3
3 7 3
4 5 1
4 6 1
4 7 1
</code></pre>
<p>a typical pseudo code for Dijkstra</p>
<pre><code>while (priority_queue not empty)  // the outer loop I'm talking about
for(neighbors of priority_queue.top())   // (E/V) *log(V)
if(good)
push into priority_queue
</code></pre>
<p>&quot;Nodes 5, 6, and 7 will each be placed in our priority queue 3 times, which is (V/2). Now, the same type of graph can definitely be made larger, which means the complexity of the outer while loop is O(V^2), and the inner code complexity is (E/V) * log(V^2), leading to a total complexity of O(E * V * log(V)) in this case scenario.&quot;</p>

CC BY-SA 4.0
2024-11-05T15:19:53.783Z
This is not a "research-level" question, so should probably be posted at cs.stackexchange.com .
Neal Young
CC BY-SA 4.0
2024-11-06T06:37:24.357Z
I don't understand what algorithm you're supposedly analyzing.  I don't what you mean by a "Dijkstra min-heap implementation" or how that relates to a graph.  Please draw a picture of the graph and include that as an image (don't force us to).  The formatting of your pseudocode seems broken (the indentation is not correct).  A single finite example cannot disprove a big-O running time, so I'm not sure what you're trying to say here.  Before posting on CS.SE, please revise the question improve it based on this feedback.
D.W.
<graph-algorithms><shortest-path>
tailored case for Dijkstra algorithm can reach O(VElog(V))
codeer
# tailored case for Dijkstra algorithm can reach O(VElog(V))

(Asked by: username_0 on 2024-11-05)

I know that this has been debated and discussed millions of times, but I couldn't find anything that explains why the outer while loop in a typical Dijkstra's min-heap implementation is considered  ()  I have created a case where it can reach (V^2)
consider this graph: (sketch it with your hand to see what I'm pointing to)
the first pair describes the edge and third number is the cost
1 2 1
1 3 2
1 4 3
2 5 6
2 6 6
2 7 6
3 5 3
3 6 3
3 7 3
4 5 1
4 6 1
4 7 1

a typical pseudo code for Dijkstra
while (priority_queue not empty)  // the outer loop I'm talking about
for(neighbors of priority_queue.top())   // (E/V) *log(V)
if(good)
push into priority_queue

"Nodes 5, 6, and 7 will each be placed in our priority queue 3 times, which is (V/2). Now, the same type of graph can definitely be made larger, which means the complexity of the outer while loop is O(V^2), and the inner code complexity is (E/V) * log(V^2), leading to a total complexity of O(E * V * log(V)) in this case scenario."

**Tags:** graph-algorithms, shortest-path

> **Comments:**
> **username_1**: This is not a "research-level" question, so should probably be posted at cs.stackexchange.com .  
> **username_2**: I don't understand what algorithm you're supposedly analyzing.  I don't what you mean by a "Dijkstra min-heap implementation" or how that relates to a graph.  Please draw a picture of the graph and include that as an image (don't force us to).  The formatting of your pseudocode seems broken (the indentation is not correct).  A single finite example cannot disprove a big-O running time, so I'm not sure what you're trying to say here.  Before posting on CS.SE, please revise the question improve it based on this feedback.  

---

## 0 answers

