
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



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



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


