<script>!function(){functiont(t){document.documentElement.setAttribute("data-theme",t)}vare=function(){try{returnnewURLSearchParams(window.location.search).get("docusaurus-theme")}catch(t){}}()||function(){try{returnlocalStorage.getItem("theme")}catch(t){}}();t(null!==e?e:"light")}(),function(){try{constc=newURLSearchParams(window.location.search).entries();for(var[t,e]ofc)if(t.startsWith("docusaurus-data-")){vara=t.replace("docusaurus-data-","data-");document.documentElement.setAttribute(a,e)}}catch(t){}}()</script><divid="__docusaurus"><divrole="region"aria-label="Skip to main content"><aclass="skipToContent_fXgn"href="#__docusaurus_skipToContent_fallback">Skip to main content</a></div><navaria-label="Main"class="navbar navbar--fixed-top"><divclass="navbar__inner"><divclass="navbar__items"><buttonaria-label="Toggle navigation bar"aria-expanded="false"class="navbar__toggle clean-btn"type="button"><svgwidth="30"height="30"viewBox="0 0 30 30"aria-hidden="true"><pathstroke="currentColor"stroke-linecap="round"stroke-miterlimit="10"stroke-width="2"d="M4 7h22M4 15h22M4 23h22"></path></svg></button><aclass="navbar__brand"href="/"><bclass="navbar__title text--truncate">mf</b></a><divclass="navbar__item dropdown dropdown--hoverable"><ahref="#"aria-haspopup="true"aria-expanded="false"role="button"class="navbar__link">Additional FI MU materials</a><ulclass="dropdown__menu"><li><aaria-current="page"class="dropdown__link dropdown__link--active"href="/algorithms/">Algorithms</a></li><li><aclass="dropdown__link"href="/c/">C</a></li><li><aclass="dropdown__link"href="/cpp/">C++</a></li></ul></div><aclass="navbar__item navbar__link"href="/contributions/">Contributions</a><aclass="navbar__item navbar__link"href="/talks/">Talks</a></div><divclass="navbar__items navbar__items--right"><aclass="navbar__item navbar__link"href="/blog/">Blog</a><divclass="toggle_vylO colorModeToggle_DEke"><buttonclass="clean-btn toggleButton_gllP toggleButtonDisabled_aARS"type="button"disabled=""title="Switch between dark and light mode (currently light mode)"aria-label="Switch between dark and light mode (currently light mode)"aria-live="polite"><svgviewBox="0 0 24 24"width="24"height="24"class="lightToggleIcon_pyhR"><pathfill="currentColor"d="M12,9c1.65,0,3,1.35,3,3s-1.35,3-3,3s-3-1.35-3-3S10.35,9,12,9 M12,7c-2.76,0-5,2.24-5,5s2.24,5,5,5s5-2.24,5-5 S14.76,7,12,7L12,7z M2,13l2,0c0.55,0,1-0.45,1-1s-0.45-1-1-1l-2,0c-0.55,0-1,0.45-1,1S1.45,13,2,13z M20,13l2,0c0.55,0,1-0.45,1-1 s-0.45-1-1-1l-2,0c-0.55,0-1,0.45-1,1S19.45,13,20,13z M11,2v2c0,0.55,0.45,1,1,1s1-0.45,1-1V2c0-0.55-0.45-1-1-1S11,1.45,11,2z M11,20v2c0,0.55,0.45,1,1,1s1-0.45,1-1v-2c0-0.55-0.45-1-1-1C11.45,19,11,19.45,11,20z M5.99,4.58c-0.39-0.39-1.03-0.39-1.41,0 c-0.39,0.39-0.39,1.03,0,1.41l1.06,1.06c0.39,0.39,1.03,0.39,1.41,0s0.39-1.03,0-1.41L5.99,4.58z M18.36,16.95 c-0.39-0.39-1.03-0.39-1.41,0c-0.39,0.39-0.39,1.03,0,1.41l1.06,1.06c0.39,0.39,1.03,0.39,1.41,0c0.39-0.39,0.39-1.03,0-1.41 L18.36,16.95z M19.42,5.99c0.39-0.39,0.39-1.03,0-1.41c-0.39-0.39-1.03-0.39-1.41,0l-1.06,1.06c-0.39,0.39-0.39,1.03,0,1.41 s1.03,0.39,1.41,0L19.42,5.99z M7.05,18.36c0.39-0.39,0.39-1.03,0-1.41c-0.39-0.39-1.03-0.39-1.41,0l-1.06,1.06 c-0.39,0.39-0.39,1.03,0,1.41s1.03,0.39,1.41,0L7.05,18.36z"></path></svg><svgviewBox="0 0 24 24"width="24"height="24"class="darkToggleIcon_wfgR"><pathfill="currentColor"d="M9.37,5.51C9.19,6.15,9.1,6.82,9.1,7.5c0,4.08,3.32,7.4,7.4,7.4c0.68,0,1.35-0.09,1.99-0.27C17.45,17.19,14.93,19,12,19 c-3.86,0-7-3.14-7-7C5,9.07,6.81,6.55,9.37,5.51z M12,3c-4.97,0-9,4.03-9,9s4.03,9,9,9s9-4.03,9-9c0-0.46-0.04-0.92-0.1-1.36 c-0.98,1.37-2.58,2.26-4.4,2.26c-2.98,0-5.4-2.42-5.4-5.4c0-1.81,0.89-3.42,2.26-4.4C12.92,3.04,12.46,3,12,3L12,3z"></path></svg></button></div><divclass="navbarSearchContainer_Bca1"><buttontype="button"class="DocSearch DocSearch-Button"aria-label="Search"><spanclass="DocSearch-Button-Container"><svgwidth="20"height="20"class="DocSearch-Search-Icon"viewBox="0 0 20 20"><pathd="M14.38614.386l4.08774.0877-4.0877-4.0877c-2.
<p>Let's rewind back to the small argument in the previous post about the fact that
we can safely bound the amount of iterations with relaxations being done.</p>
<p>We have said that assuming the worst-case scenario (bad order of relaxations) we
<strong>need</strong> at most <spanclass="katex"><spanclass="katex-mathml"><mathxmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mimathvariant="normal">∣</mi><mi>V</mi><mimathvariant="normal">∣</mi><mo>−</mo><mn>1</mn></mrow><annotationencoding="application/x-tex">\vert V \vert - 1</annotation></semantics></math></span><spanclass="katex-html"aria-hidden="true"><spanclass="base"><spanclass="strut"style="height:1em;vertical-align:-0.25em"></span><spanclass="mord">∣</span><spanclass="mord mathnormal"style="margin-right:0.22222em">V</span><spanclass="mord">∣</span><spanclass="mspace"style="margin-right:0.2222em"></span><spanclass="mbin">−</span><spanclass="mspace"style="margin-right:0.2222em"></span></span><spanclass="base"><spanclass="strut"style="height:0.6444em"></span><spanclass="mord">1</span></span></span></span> iterations over all edges. We've used that
to our advantage to <em>bound</em> the iterations instead of the <code>do-while</code> loop that
was a risk given the possibility of the infinite loop (when negative loops are
happened and the upper bound of iterations, for some graphs that would result in
faster termination.</p><p>Using only the upper bound we try to relax edges even though we can't.</p></div></div>
<p>Now the question arises, could we leverage this somehow in a different way? What
if we used it to improve the algorithm instead of just bounding the iterations?
Would that be even possible?</p>
<p><strong>Yes, it would!</strong> And that's when <em>Dijkstra's algorithm</em> comes in.</p>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="dijkstras-algorithm">Dijkstra's algorithm<ahref="#dijkstras-algorithm"class="hash-link"aria-label="Direct link to Dijkstra's algorithm"title="Direct link to Dijkstra's algorithm"></a></h2>
<p>I'll start with a well-known meme about Dijkstra's algorithm:
a requirement of <em>no edges with negative weights</em> in the graph. This
precondition is required because of the nature of the algorithm that requires
monotonically non-decreasing changes in the costs of shortest paths.</p></div></div>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="short-description">Short description<ahref="#short-description"class="hash-link"aria-label="Direct link to Short description"title="Direct link to Short description"></a></h2>
<p>Let's have a brief look at the pseudocode taken from the Wikipedia:</p>
<p>Dijkstra's algorithm works in such way that it always tries to find the shortest
paths from a vertex to which it already has a shortest path. This may result in
finding the shortest path to another vertex, or at least some path, till further
relaxation.</p>
<p>Given that we need to <strong>always</strong> choose the <em>cheapest</em> vertex, we can use a min
heap to our advantage which can further improve the time complexity of the
algorithm.</p>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="used-techniques">Used techniques<ahref="#used-techniques"class="hash-link"aria-label="Direct link to Used techniques"title="Direct link to Used techniques"></a></h2>
<p>This algorithm leverages the <em>dynamic programming</em> technique that has already
been mentioned with regards to the <em>Bellman-Ford</em> algorithm and also <em>greedy</em>
technique. Let's talk about them both!</p>
<p><em>Dynamic programming</em> technique comes from the fact that we are continuously
building on top of the shortest paths that we have found so far. We slowly build
the shortest paths from the given source vertex to all other vertices that are
reachable.</p>
<p><em>Greedy</em> technique is utilized in such way that Dijkstra's algorithm always
improves the shortest paths from the vertex that is the closest, i.e. it tries
extending the shortest path to some vertex by appending an edge, such extended
path may (or may not) be the shortest path to another vertex.</p>
<p>The reason why the algorithm requires no edges with negative weights comes from
the fact that it's greedy. By laying the requirement of non-negative weights in
the graph we are guaranteed that at any given moment of processing outgoing
edges from a vertex, we already have a shortest path to the given vertex. This
means that either this is the shortest path, or there is some other vertex that
may have a higher cost, but the outgoing edge compensates for it.</p>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="implementation">Implementation<ahref="#implementation"class="hash-link"aria-label="Direct link to Implementation"title="Direct link to Implementation"></a></h2>
<p>Firstly we need to have some priority queue wrappers. C++ itself offers
functions that can be used for maintaining max heaps. They also have generalized
version with any ordering, in our case we need reverse ordering, because we need
<h2class="anchor anchorWithStickyNavbar_LWe7"id="time-complexity">Time complexity<ahref="#time-complexity"class="hash-link"aria-label="Direct link to Time complexity"title="Direct link to Time complexity"></a></h2>
<p>The time complexity of Dijkstra's algorithm differs based on the backing data
structure.</p>
<p>The original implementation doesn't leverage the heap which results in
repetitive <em>look up</em> of the “closest” vertex, hence we get the following
worst-case time complexity in the <em>Bachmann-Landau</em> notation:</p>
<spanclass="katex-display"><spanclass="katex"><spanclass="katex-mathml"><mathxmlns="http://www.w3.org/1998/Math/MathML"display="block"><semantics><mrow><mimathvariant="normal">Θ</mi><mostretchy="false">(</mo><mimathvariant="normal">∣</mi><mi>V</mi><msup><mimathvariant="normal">∣</mi><mn>2</mn></msup><mostretchy="false">)</mo></mrow><annotationencoding="application/x-tex">\Theta(\vert V \vert^2)</annotation></semantics></math></span><spanclass="katex-html"aria-hidden="true"><spanclass="base"><spanclass="strut"style="height:1.1141em;vertical-align:-0.25em"></span><spanclass="mord">Θ</span><spanclass="mopen">(</span><spanclass="mord">∣</span><spanclass="mord mathnormal"style="margin-right:0.22222em">V</span><spanclass="mord"><spanclass="mord">∣</span><spanclass="msupsub"><spanclass="vlist-t"><spanclass="vlist-r"><spanclass="vlist"style="height:0.8641em"><spanstyle="top:-3.113em;margin-right:0.05em"><spanclass="pstrut"style="height:2.7em"></span><spanclass="sizing reset-size6 size3 mtight"><spanclass="mord mtight">2</span></span></span></span></span></span></span></span><spanclass="mclose">)</span></span></span></span></span>
<p>If we turn our attention to the backing data structure, we always want the
“cheapest” vertex, that's why we can use the min heap, given that we use
Fibonacci heap we can achieve the following amortized time complexity:</p>
<spanclass="katex-display"><spanclass="katex"><spanclass="katex-mathml"><mathxmlns="http://www.w3.org/1998/Math/MathML"display="block"><semantics><mrow><mimathvariant="script">O</mi><mostretchy="false">(</mo><mimathvariant="normal">∣</mi><mi>E</mi><mimathvariant="normal">∣</mi><mo>+</mo><mimathvariant="normal">∣</mi><mi>V</mi><mimathvariant="normal">∣</mi><mo>⋅</mo><mi>log</mi><mo></mo><mrow><mimathvariant="normal">∣</mi><mi>V</mi><mimathvariant="normal">∣</mi></mrow><mostretchy="false">)</mo></mrow><annotationencoding="application/x-tex">\mathcal{O}(\vert E \vert + \vert V \vert \cdot \log{\vert V \vert})</annotation></semantics></math></span><spanclass="katex-html"aria-hidden="true"><spanclass="base"><spanclass="strut"style="height:1em;vertical-align:-0.25em"></span><spanclass="mord mathcal"style="margin-right:0.02778em">O</span><spanclass="mopen">(</span><spanclass="mord">∣</span><spanclass="mord mathnormal"style="margin-right:0.05764em">E</span><spanclass="mord">∣</span><spanclass="mspace"style="margin-right:0.2222em"></span><spanclass="mbin">+</span><spanclass="mspace"style="margin-right:0.2222em"></span></span><spanclass="base"><spanclass="strut"style="height:1em;vertical-align:-0.25em"></span><spanclass="mord">∣</span><spanclass="mord mathnormal"style="margin-right:0.22222em">V</span><spanclass="mord">∣</span><spanclass="mspace"style="margin-right:0.2222em"></span><spanclass="mbin">⋅</span><spanclass="mspace"style="margin-right:0.2222em"></span></span><spanclass="base"><spanclass="strut"style="height:1em;vertical-align:-0.25em"></span><spanclass="mop">lo<spanstyle="margin-right:0.01389em">g</span></span><spanclass="mspace"style="margin-right:0.1667em"></span><spanclass="mord"><spanclass="mord">∣</span><spanclass="mord mathnormal"style="margin-right:0.22222em">V</span><spanclass="mord">∣</span></span><spanclass="mclose">)</span></span></span></span></span>
insertion and <spanclass="katex"><spanclass="katex-mathml"><mathxmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mimathvariant="script">O</mi><mostretchy="false">(</mo><mi>log</mi><mo></mo><mi>n</mi><mostretchy="false">)</mo></mrow><annotationencoding="application/x-tex">\mathcal{O}(\log{n})</annotation></semantics></math></span><spanclass="katex-html"aria-hidden="true"><spanclass="base"><spanclass="strut"style="height:1em;vertical-align:-0.25em"></span><spanclass="mord mathcal"style="margin-right:0.02778em">O</span><spanclass="mopen">(</span><spanclass="mop">lo<spanstyle="margin-right:0.01389em">g</span></span><spanclass="mspace"style="margin-right:0.1667em"></span><spanclass="mord"><spanclass="mord mathnormal">n</span></span><spanclass="mclose">)</span></span></span></span><strong>amortized</strong> removal of the top (either
min or max).</p></div></div>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="running-the-dijkstra">Running the Dijkstra<ahref="#running-the-dijkstra"class="hash-link"aria-label="Direct link to Running the Dijkstra"title="Direct link to Running the Dijkstra"></a></h2>
<p>OK, so it seems to be working just fine. Now the question arises:</p>
<blockquote>
<p>What happens when we have negative weights in our graph?</p>
</blockquote>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="busting-the-myth-about-looping-dijkstra">Busting the myth about looping Dijkstra<ahref="#busting-the-myth-about-looping-dijkstra"class="hash-link"aria-label="Direct link to Busting the myth about looping Dijkstra"title="Direct link to Busting the myth about looping Dijkstra"></a></h2>
<p>One of the very common misconception about Dijkstra's algorithm is that it loops
infinitely when you have negative weights or loops in the graph. Well, if we use
our <em>propelling vortices</em>, not only we have the negative weights, but also the
negative loops. Let's run our code! Our first naïve approach was actually
it in such way that with negative weights or loops it loops infinitely, but it
can be countered. In our case we keep the track of the vertices that already got
a shortest path established via the <code>visited</code>, that's how even multiple entries
for one vertex in the heap are not an issue.</p></div></div>
<h2class="anchor anchorWithStickyNavbar_LWe7"id="summary">Summary<ahref="#summary"class="hash-link"aria-label="Direct link to Summary"title="Direct link to Summary"></a></h2>
<p>Now we have an algorithm for finding the shortest path that is faster than our
original naïve brute-force or Bellman-Ford. However we need to keep in mind its
requirement of no negative weights for correct functioning.</p>
<p>You can also see how we used our thought process of figuring out the worst-case
time complexity for the naïve or Bellman-Ford algorithm to improve the original
