Comments (10)
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?
Original comment by [email protected]
on 9 Jun 2014 at 6:05
from java-algorithms-implementation.
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]>:
Original comment by [email protected]
on 9 Jun 2014 at 6:22
from java-algorithms-implementation.
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?
Original comment by [email protected]
on 9 Jun 2014 at 7:44
from java-algorithms-implementation.
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.
Original comment by [email protected]
on 9 Jun 2014 at 7:47
Attachments:
from java-algorithms-implementation.
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
Original comment by [email protected]
on 9 Jun 2014 at 7:59
from java-algorithms-implementation.
you parsed the files incorrectly
1 80,982 here edge is 1-80 with cost 982
Note there are 300 vertices only.
Original comment by [email protected]
on 9 Jun 2014 at 8:01
from java-algorithms-implementation.
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.
Original comment by [email protected]
on 9 Jun 2014 at 8:11
from java-algorithms-implementation.
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.
Original comment by [email protected]
on 9 Jun 2014 at 8:16
from java-algorithms-implementation.
No problem. Keep it up. A good library, I will continue using it. I want to
work on Segment Trees for RMQ next.
Original comment by [email protected]
on 9 Jun 2014 at 8:18
from java-algorithms-implementation.
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.
Original comment by [email protected]
on 9 Jun 2014 at 10:26
- Changed state: Fixed
from java-algorithms-implementation.
Related Issues (7)
- Patch for /trunk/src/com/jwetherell/algorithms/data_structures/BTree.java HOT 2
- Prim.java HOT 4
- ArrayQueue has a NPE HOT 4
- XYZPoint 3-value constructor takes int for y (instead of double) HOT 1
- An Interval Tree query on range is not guaranteed to return all matches HOT 3
- BTree addition freezes when adding duplicate value HOT 3
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from java-algorithms-implementation.