0

I'm trying to run Dijkstra's algorithm and I need to implement a decreaseKey function. I'm having trouble doing it. I read one solution here but it uses a lot of memory by storing a hash map in the heap. Is there a way to implement decreaseKey without a hash map and still maintain O(log n) time?

So far my decreaseKey function takes two parameters: vertex and newDistance. When I call decreaseKey(vertex * v, int newDistance), the algorithm has to find the index where vertex 'v' is stored and then change its distance. I can't figure out how to 'find' the vertex to get its index and keep it in O(log n) time.

Community
  • 1
  • 1
David Velasquez
  • 2,346
  • 1
  • 26
  • 46

1 Answers1

0

You don't need a hash map to store the information; you only need a mapping from vertex to priority-queue position. If your vertices are identified by consecutive integers, then the mapping consists of an array of |V| integers (where |V| is the number of vertices).

While that is not a trivial amount of space, it is only one word per graph vertex, which is considerably less than the space occupied by edge lists.

rici
  • 234,347
  • 28
  • 237
  • 341
  • Sorry I'm not following your answer. My vertices are named as integers but I don't understand what you mean that they can be mapped to their priority queue position. Wouldn't their position and their name be at different locations? – David Velasquez Nov 11 '15 at 23:30
  • @ghost: if you can find the name of the vertex from the `vertex *v`, then you can use the name to get the position in the pq by using the name as an index into the mapping table. One way to do this is to keep all the vertices in a `vertex[]`, in which case you can compute the name as `v - vbase`. Another way is to keep the name in the `vertex` struct. Either way, the pq can maintain the mapping while it is shuffling elements, so the only incremental cost is the vertex-id to pq position mapping. – rici Nov 11 '15 at 23:42