Ivan-Mark Debono - 10 months ago 64

Java Question

I found this implementation (relevant part follows) of Dijkstra using priority queue. Is it possible to speed it up further by implement Fibonacci heaps or even moving to Iterative Deepening A*?

`47 public static void computePaths(Vertex source)`

48 {

49 source.minDistance = 0.;

50 PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();

51 vertexQueue.add(source);

52

53 while (!vertexQueue.isEmpty()) {

54 Vertex u = vertexQueue.poll();

55

56 // Visit each edge exiting u

57 for (Edge e : u.adjacencies)

58 {

59 Vertex v = e.target;

60 double weight = e.weight;

61 double distanceThroughU = u.minDistance + weight;

62 if (distanceThroughU < v.minDistance) {

63 vertexQueue.remove(v);

64

65 v.minDistance = distanceThroughU ;

66 v.previous = u;

67 vertexQueue.add(v);

68 }

69 }

70 }

71 }

Answer

Yes, you can.

The suggested implementation has a major performance flaw:

```
62 if (distanceThroughU < v.minDistance) {
63 vertexQueue.remove(v);
64
65 v.minDistance = distanceThroughU ;
66 v.previous = u;
67 vertexQueue.add(v);
68 }
```

The problem with this piece of code, is removing an arbitrary (not the root) node `v`

from a the priority queue is done in linear time. Java Docs:

Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add);

linear time for the remove(Object)and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size).

In a fibonacci heap however, you can change the priority of a node much more efficiently.