Fastest Dijkstra algorithm for j2ME

Question

Hi All,

Can anybody help me to make j2ME implementation of Dijkstra algorithm faster ? I have two loops, one inside another. Like this

while(for each item in Q)
{
    //...do something.

    //the following loop is to find the minimum
    for(all un-visited nodes in Q)
    {
       //.. do something to get min.
    }

}

I have almost 23000 nodes and 50000 edges connecting them...The inner loop executes an average of 169330131 times after all improvements mentioned below. This takes 5 minutes to complete on my w910i mobile and more than minutes on my emulator. This looks too much for me. Any suggestions for improvement? I have the following improvements already implemented.

1. Using array instead of vector.
2. Make sure that the inner loop does not consider the visited nodes. All my visited nodes are at the end of the array and I node know the count. So, I can easily skip them altogether.

Thanks in advance

D M

Answer 1

Something wrong with your implementation. It's complexity is O(E + V * log2 (V)).

That means 50000 + 23000 * ~15 = 400 000 iterations.

Your current complexity is almost O(V^2).

Answer 2

I think your algorithm in the question is wrong. The inner loop should be looking at each unvisited neighbour of the item in the outer loop:

for each (item in Q)
{
  for each (unvisited neighbour of item)
  {
  }
}

Compare it with the pseudocode implementation in wikipedia:

 1  function Dijkstra(Graph, source):
 2      for each vertex v in Graph:           // Initializations
 3          dist[v] := infinity               // Unknown distance function from source to v
 4          previous[v] := undefined          // Previous node in optimal path from source
 5      dist[source] := 0                     // Distance from source to source
 6      Q := the set of all nodes in Graph
        // All nodes in the graph are unoptimized - thus are in Q
 7      while Q is not empty:                 // The main loop
 8          u := vertex in Q with smallest dist[]
 9          if dist[u] = infinity:
10              break                         // all remaining vertices are inaccessible
11          remove u from Q
12          for each neighbor v of u:         // where v has not yet been removed from Q.
13              alt := dist[u] + dist_between(u, v) 
14              if alt < dist[v]:             // Relax (u,v,a)
15                  dist[v] := alt
16                  previous[v] := u
17      return previous[]

Answer 3

I referred this algorithm. I found a simpler algorithm some other place. Please note that If I had to implement the one in Wikipedia, there are two inner loops.

while Q is not empty: //Outer loop. 
  u := vertex in Q with smallest dist[];// First inner loop. 
  .... 
  for each neighbor v of u: //Second inner loop.

The second inner loop is smaller. It might execute a maximum of 4-5 as there are at most 5 edges for each node. The number of nodes having more than 2 edges is 1000 out of 23000 total nodes. So, the execution time for inner loop is negligible. The first inner loop is the problem. Finding the smallest node. As I have to execute this on a j2ME device, I have to make it to take as much less space as possible.

Answer 4

Hello Deekshit,

have you solved your complexity problems with Dijkstra algorithm?

I would need an efficient implementation for J2ME too. Is your solution an open source? ;)

Regards Mobile Developer [email protected]