Dijkstra doesn't work about java-algorithms-implementation HOT 10 CLOSED

Line 103 in Dijkstra.java removes the element from the priority queue.

Graph.CostVertexPair<Integer> pair = unvisited.remove();

I'll try and test with your data but can you explain the format of the attached 
data file?

This line removes element from top of the queue. It's fine. But when some
other element (in the middle of the heap) is updated, for example like
this: pair.setCost(cost);
Its priority is not updated in the heap and it must be removed from the
queue and readded again.

Test file description: each line starts with a vertex id the follows id of
andjacent vertex and cost of the edge, for example this 1 80,982 163,8164
means thar vertex 1 adjacent to 80 (cost=982) and 163 (cost=8164). I'm
attaching my test to reproduce the problem, correct output must be
2599,2610,2947,2052,2367,2399,2029,2442,2505,3068,

Let me know if you have questions


2014-06-09 22:05 GMT+04:00 <[email protected]>:

Wait.. Did you forget to attach something? In reference to:

"I'm attaching my test to reproduce the problem, correct output must be
2599,2610,2947,2052,2367,2399,2029,2442,2505,3068"

What is the input for that output? Going from which to which vertex?

Looks like attaching via email reply doesn't work here. Attaching directly.
The numbers are for shortest paths from 1 to 7,37,59,82,99,115,133,165,188,197 
respectively.

ok, I've updated the Dijkstra code with your fix but I am getting a different 
result. For example, going from vertex 1 to vertex 7:

Cost = 50
    edge: [1] -> [1913] = 11
    edge: [1913] -> [11] = 1
    edge: [11] -> [8988] = 10
    edge: [8988] -> [10] = 11
    edge: [10] -> [2904] = 7
    edge: [2904] -> [7] = 10

you parsed the files incorrectly 
1 80,982 here  edge is 1-80 with cost 982
Note there are 300 vertices only.

shortest path for 1->7 must be as following:
1 -> 114 508
114 -> 129 168
129 -> 85 517
85 -> 53 1227
53 -> 7 179

Note: I wanted to use the library as it doesn't do this remove on update (since 
it takes O(N) in PriorityQueue rather than O(logN) which is time it should take 
for a heap). So I decided to make my own heap implementation for fast removal. 
If you want I can share a code. It runs 2 times faster than an algo with 
PriorityQueue on the provided test sample.

Ah OK, you are correct. I found the problem (as you pointed out) and fixed it. 
I am apprehensive about the fix before it has to remove (an O(N) operation) and 
then insert into the priority heap (which is a O(log n) operation). I am still 
evaluating the alternatives.

But THANKS for pointing this out. 

No problem. Keep it up. A good library, I will continue using it. I want to 
work on Segment Trees for RMQ next.

Once again, thanks for pointing out the bug and please send me your version of 
a heap; I'll likely not use it in the Dijkstra code because I like to keep the 
code mostly dependent on JRE Collections but I am interested. 

I have committed the changes for the bug you reported, if you can please update 
to the latest and run it against your version and let me know the time 
difference, I am curious.

Also, please report any problems/limitations on the segment tree. The segment 
tree and the interval tree are the least tested of the data structures in this 
library.