[solved] A case where dijkstra_shortest_paths fails (due to the negative weight)

Specific Domains Optimization (Mathematical)
1

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.

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")
2

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?

2 Likes
3

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

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.

2 Likes
4

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!

1 Like
5

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