Dijkstra Algorithm in Java

1
votes

I have some troubles implementing Dijkstra algorithm in Java.
I use this (first) pseudocode: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Line 15 you need to get the vertex with the lowest distance. But how can I save the distance with the according distance.
Note: vertex is defined as an Integer.

My solutions that didn't work properly:

  1. Map with K = vertex, V = distance, Problem: long searching to get min dist
  2. SortedMap with K = distance, V = vertex, Problem: almost every distance is defined as Integer.MAX_VALUE

So I am looking for a fast way to save a vertex to a distance and it should be easy to get the vertex with min dist.

1
javaalgorithmdata-structuresdijkstra
I don't think u can find something faster than Map for you solution - nafas
alternatively you could use some already implemented graph structures for java - nafas
So the best solution is actually a SortedMap with K=distance and V=List Integer(=vertex)? - fangio
Fangio SortedMap sounds good but only problem with it will be it will not auto update the relaxed costs. Only while inserting it will put the vertex in correct order of its cost but as the cost gets relaxed then retrieving may have some issues as node retrieved may not be the one with lowest cost. So Own Min Heap should be implemented. The problem I mentioned with SortedMap is also there in the java.util.PriorityQueue. - nits.kk

1 Answers

0
votes

Try using a PriorityQueue. That way, you can simply remove the head, as it would have the minimum distance of all vertices.

See more information about PriorityQueue here: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html