Possible bug in Dijkstra algorithm?

Topics: algorithm, bug
Nov 12, 2008 at 7:33 AM
Hi everyone:

We are working with version 2.x of Quickgraph, i am aware that you don't provide any support for old 2.x code any more but i have a problem with Dijkstra Algorithm and maybe you would be so kind to answer me a simple question.

Our problem is that we have implemented an A algorithm and testing the shortest path from our algorithm against Dijkstra result we are noticing that sometimes the result from Dijkstra is a larger path than the A one.

I have to point that our A algorithm implementation doesn't use any type of heuristic function and we are using a quite huge graph, that is around 25000 nodes and 70000 arcs.

I've been seeking for source code changes on 3.0 and haven't seen any changes on the algorithm.

Are you aware about any possible bugs on the Dijkstra implementation or its just my algorithm which is wrong?

Sincerely,

Miguel Angel.


PS: here is a sample of our results in testing, its a log from a computer which is iterating shortest path from random "Vertice1" to random "Vertice2" on both algorithms:

result is not equal: Cost: A = 7735,2; Dijkstra = 7737,7

result is not equal: Cost: A = 3556; Dijkstra = 3579

result is equal.

result is not equal: Cost: A = 5068,2; Dijkstra = 5072,2

result is not equal: Cost: A= 7768; Dijkstra = 7977

result is equal.

result is equal.

result is equal.

result is not equal: Cost: A = 5527; Dijkstra = 5410
Nov 13, 2008 at 7:30 AM
I also am having some strange results.
I am guessing that you are using the bidirectionalGraph, as Undirected.Dijkstra does not work at this time.

My needs are for an undirected graph.  Using the hopefully functional Bidrectional, all edges have been added twice with swapped vertices
I do not care about dead end points.  So for faster run times, I remove them - saves about 30% of cpu time..
ie: 
    For Each Vertex As PointVertex In Graph.Vertices
            If Graph.InDegree(Vertex) = 1 Then
                If Graph.OutDegree(Vertex) = 1 Then
                        Dim Tag As Integer = Graph.OutEdge(Vertex, 0).Tag
                        DeadEdges.Add(Tag) ' do not want to kill the iterator deleting here
                        DeadEndsThisPass = DeadEndsThisPass + 1
                End If
            End If
    Next
    Remove the DeadEdges from the graph

Since entering a vertice, which has only one way out (the entrance), will not get us a shorter path to ANYWHERE,
I feel strongly that it should not affect the results of the shortest path process.

This is not the case..
Deads Ends REMOVED
=================================
Shortest path from 0 to 1: Edges = 209   Distance = 18.6871025766148
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 229   Distance = 25.1420981198549
Shortest path from 0 to 4: Edges = 279   Distance = 30.185930068833
Shortest path from 0 to 5: Edges = 278   Distance = 30.1852232020982
Shortest path from 0 to 6: Edges = 279   Distance = 30.1909297394133
Shortest path from 0 to 7: Edges = 282   Distance = 30.0787995138543
Shortest path from 0 to 8: Edges = 281   Distance = 30.0036287763947
Shortest path from 0 to 9: Edges = 280   Distance = 29.9563015749597
Shortest path from 0 to 10: Edges = 285   Distance = 30.1029364471016
Shortest path from 0 to 11: Edges = 284   Distance = 30.100420657676
Shortest path from 0 to 12: Edges = 279   Distance = 30.0861420986841
Shortest path from 0 to 13: Edges = 278   Distance = 30.080859530371
Shortest path from 0 to 14: Edges = 277   Distance = 30.078852230681
Shortest path from 0 to 15: Edges = 276   Distance = 30.0748250836192
Shortest path from 0 to 16: Edges = 275   Distance = 30.0647169042368
Shortest path from 0 to 17: Edges = 276   Distance = 30.066050328606
Shortest path from 0 to 18: Edges = 276   Distance = 30.0703928405923
Shortest path from 0 to 19: Edges = 277   Distance = 30.0762113850632
Shortest path from 0 to 20: Edges = 278   Distance = 30.0822445408384
Shortest path from 0 to 21: Edges = 283   Distance = 30.1869257130482
Shortest path from 0 to 22: Edges = 283   Distance = 30.0977362529961
Shortest path from 0 to 23: Edges = 280   Distance = 30.0916260071138
Shortest path from 0 to 24: Edges = 281   Distance = 30.1977373594932
Shortest path from 0 to 25: Edges = 280   Distance = 30.1967825679065
Shortest path from 0 to 26: Edges = 281   Distance = 30.0929290774213
Shortest path from 0 to 27: Edges = 282   Distance = 30.0941029083026
Shortest path from 0 to 28: Edges = 230   Distance = 25.2547387461507
Shortest path from 0 to 29: Edges = 230   Distance = 25.1470488312715
Shortest path from 0 to 30: Edges = 229   Distance = 25.249641895234
Shortest path from 0 to 31: Edges = 374   Distance = 31.2457734131495
Shortest path from 0 to 32: Edges = 207   Distance = 18.9107195764928
Shortest path from 0 to 33: Edges = 208   Distance = 18.9195743423705
Shortest path from 0 to 34: Edges = 206   Distance = 18.8739869214042
Shortest path from 0 to 35: Edges = 210   Distance = 18.6878648595076


Dead Ends PRESENT
============================
Shortest path from 0 to 1: Edges = 227   Distance = 19.0100456527529
Shortest path from 0 to 2:   No Path
Shortest path from 0 to 3: Edges = 261   Distance = 26.5644314427133
Shortest path from 0 to 4: Edges = 314   Distance = 31.6082941722276
Shortest path from 0 to 5: Edges = 313   Distance = 31.6075873054928
Shortest path from 0 to 6: Edges = 314   Distance = 31.6132938428079
Shortest path from 0 to 7: Edges = 318   Distance = 31.7467679565931
Shortest path from 0 to 8: Edges = 316   Distance = 31.4259928797893
Shortest path from 0 to 9: Edges = 315   Distance = 31.3786656783543
Shortest path from 0 to 10: Edges = 316   Distance = 31.3790951118068
Shortest path from 0 to 11: Edges = 314   Distance = 31.3868351149137
Shortest path from 0 to 12: Edges = 309   Distance = 31.3725565559218
Shortest path from 0 to 13: Edges = 308   Distance = 31.3672739876087
Shortest path from 0 to 14: Edges = 307   Distance = 31.3652666879187
Shortest path from 0 to 15: Edges = 306   Distance = 31.3612395408569
Shortest path from 0 to 16: Edges = 305   Distance = 31.3511313614745
Shortest path from 0 to 17: Edges = 305   Distance = 31.3507770247126
Shortest path from 0 to 18: Edges = 304   Distance = 31.3449197391847
Shortest path from 0 to 19: Edges = 305   Distance = 31.3507382836556
Shortest path from 0 to 20: Edges = 306   Distance = 31.3567714394308
Shortest path from 0 to 21: Edges = 317   Distance = 31.6386417573992
Shortest path from 0 to 22: Edges = 313   Distance = 31.3841507102338
Shortest path from 0 to 23: Edges = 310   Distance = 31.3780404643515
Shortest path from 0 to 24: Edges = 316   Distance = 31.6201014628878
Shortest path from 0 to 25: Edges = 315   Distance = 31.6191466713011
Shortest path from 0 to 26: Edges = 311   Distance = 31.379343534659
Shortest path from 0 to 27: Edges = 312   Distance = 31.3805173655403
Shortest path from 0 to 28: Edges = 262   Distance = 26.6770720690091
Shortest path from 0 to 29: Edges = 262   Distance = 26.5693821541298
Shortest path from 0 to 30: Edges = 261   Distance = 26.6719752180924
Shortest path from 0 to 31: Edges = 341   Distance = 14.0733716554419
Shortest path from 0 to 32: Edges = 206   Distance = 20.449694441428
Shortest path from 0 to 33: Edges = 207   Distance = 20.4585492073057
Shortest path from 0 to 34: Edges = 205   Distance = 20.4129617863394
Shortest path from 0 to 35: Edges = 228   Distance = 19.0108079356457
Nov 14, 2008 at 3:03 AM
After downloading and referencing the current stock 3.0 release (source version 17438)
I get identical answers with dead ends present, or not.
Coordinator
Nov 20, 2008 at 4:49 AM
This discussion has been copied to a work item. Click here to go to the work item and continue the discussion.
Coordinator
Dec 3, 2008 at 6:51 PM
This bug should be fixed now. There was a bug with the new fibonacci heap.

Cross-tested Dijkstra with Floyd-Warshall algorithm on many GraphML sample graphs.