# \[solved\] A case where dijkstra\_shortest\_paths fails (due to the negative weight)

**URL:** <https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564>\
**Category:** Optimization (Mathematical)\
**Tags:** graphs\
**Created:** [June 10, 2022, 1:11pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564 "2022-06-10T13:11:24Z")\
**Posts on this page:** 5\
**Page:** 1

<div class="post-metadata">

**Author:** ![HanBBer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hanbber/32/35557_2.png) [@HanBBer](https://discourse.julialang.org/u/HanBBer)\
**Post date:** [June 10, 2022, 1:11pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564/1 "2022-06-10T13:11:24Z")

</div>

I’m unsure if the Dijkstra algorithm should quit for any proper case. But it got stuck during my work, and attached belong is a code for reproducing.

```julia
using Graphs

node1 = [1 1 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 8 8 8 8 9 9 9 10 10 10 10 10 11 11 11 11 12 12 12 13 13 14 14 14 15 15 15 15 16 16 16 16 17 17 17 18 18 18 19 19 19 20 20 20 20 21 21 21 22 22 22 22 23 23 23 24 24 24]

node2 = [2 3 1 6 1 4 12 3 5 11 4 6 9 2 5 8 8 18 6 7 9 16 5 8 10 9 11 15 16 17 4 10 12 14 3 11 13 12 24 11 15 23 10 14 19 22 8 10 17 18 10 16 19 7 16 20 15 17 20 18 19 21 22 20 22 24 15 20 21 23 14 22 24 13 21 23]

v = [0.15665259084095626, 0.11812474914919661, 0.17023098808459436, 0.2900482428853247, 0.10444058907013831, 0.07804486509753934, 0.1658484726920056, 0.14690574809769782, -0.014720078435575795, 0.23416402271848297, 0.01335079849911272, 0.5033173233688677, 0.4604213927242876, 0.3238740318606045, 0.3952241156480858, 0.5791298591791296, 0.3039041854626014, 0.0813201085529375, 0.4908572001365739, 0.3274329024704454, 0.7738206719783498, 0.5298835703508152, 0.6001590858008188, 0.6054064370709313, 0.24682016239479965, 0.28439289166284387, 0.7179915547229211, 0.6641140501352303, 0.6820936318447326, 0.954685152742369, 0.2789748610554565, 0.702458160817335, 0.7115012729275033, 0.7579341103276315, 0.08307709465424826, 0.7291905259980036, 0.14603827720710927, 0.06344340350792939, 0.6448040009102016, 0.8182339066326351, 0.6641021928411512, 0.43894259346390624, 0.7204573352053428, 0.6725877562809711, 0.16527015924822205, 0.4193785543177752, 0.6093867674772457, 0.6393729711915905, 0.5509501188461728, 0.08029672994371498, 1.0059919867785596, 0.539928276561037, 0.3984731392149453, 0.04489022900956791, 0.09661283042288668, 0.13545469887198167, 0.16697911352142508, 0.4157712649084892, 0.5636205135884604, 0.11612014110042433, 0.5351063915190762, 0.3743566297855155, 0.3749065736159266, 0.33657152692524495, 0.22394117942511715, 0.7318265674308344, 0.4889036126407987, 0.39077391963901764, 0.21384841092865614, 0.7082702508633052, 0.5060176518325535, 0.7831860608879805, 0.1770960865196909, 0.5466756286060043, 0.667779614258025, 0.29450686257781533]

no_node = max(maximum(node1), maximum(node2))
no_arc = Base.length(node1)

graph = DiGraph(no_node)
for i=1:no_arc
    add_edge!(graph, node1[i], node2[i])
end

distmx = Inf*ones(no_node, no_node)
for i in 1:no_arc
    distmx[node1[i], node2[i]] = v[i]
end

println("build tree")
state = dijkstra_shortest_paths(graph, 7, distmx)
println("tree done")

```

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [June 10, 2022, 2:06pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564/2 "2022-06-10T14:06:21Z")

</div>

Hi! I can reproduce this behavior, but it is not a bug.  
Indeed, you cannot apply Dijkstra’s algorithm when there are negative edge weights, otherwise it might loop forever. Since you have negative edge weights, the problem may be much harder than you anticipated. Can I ask what the application is, and where the negative weights come from?

---

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 10, 2022, 2:20pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564/3 "2022-06-10T14:20:05Z")

</div>

If you have negative edge weights, you should use the Bellman–Ford algorithm instead (or something derived from it):

> **[Bellman–Ford algorithm](https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm)**
>
> The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph.
> It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.
> The algorithm was first proposed by Alfonso Shimbel (1955), but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.\[ Ne...

Assuming there are no negative cycles in your graph (which create unbounded shortest-path costs), this algorithm runs in O(nm) time (so it is fairly efficient), and it is easy to spot unboundedness if it arises.

The correctness proof for Dijkstra’s depends innately on having nonnegative edge weights.

---

<div class="post-metadata">

**Author:** ![HanBBer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hanbber/32/35557_2.png) [@HanBBer](https://discourse.julialang.org/u/HanBBer)\
**Post date:** [June 10, 2022, 2:21pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564/4 "2022-06-10T14:21:32Z")

</div>

Thanks a lot!  
It’s actually an application about assignment problems.  
However, I forgot to check the sign before using Dijkstra, the negative weights should never happen and I will check my algorithm carefully.  
Thank you again!

---

<div class="post-metadata">

**Author:** ![HanBBer](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hanbber/32/35557_2.png) [@HanBBer](https://discourse.julialang.org/u/HanBBer)\
**Post date:** [June 10, 2022, 2:25pm UTC](https://discourse.julialang.org/t/solved-a-case-where-dijkstra-shortest-paths-fails-due-to-the-negative-weight/82564/5 "2022-06-10T14:25:32Z")

</div>

Thank you for your suggestion! I would like to check my algorithm carefully and I made a note for the Bellman-Ford algorithm, thanks!