Fastest Dijkstra's algorithm for j2ME
Can anyone help me to execute the j2ME implementation of Dijkstra's algorithm faster? I have two loops, one inside. 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 23,000 nodes and 50,000 edges connecting them ... The inner loop runs 169330131 times on average after all the improvements mentioned below. It takes 5 minutes to complete my w910i mobile and more than minutes on my emulator. This is too much for me. Any suggestions for improvement? I already have the following improvements.
- Using an array instead of a vector.
- Make sure the inner loop does not count the nodes visited. All my visited nodes are at the end of the array, and I node knows the count. So I can easily skip them altogether.
a source to share
I think your algorithm in the question is wrong. The inner loop must look at every invisible neighbor of the element in the outer loop:
for each (item in Q)
{
for each (unvisited neighbour of item)
{
}
}
Compare it to 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[]
a source to share
I named this algorithm. I found a simpler algorithm elsewhere. Note that if I had to implement the one on 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 can do 4-5 at most since there are at most 5 edges for each node. The number of nodes with more than 2 edges is 1000 out of 23000 common nodes. Thus, the execution time for the inner loop is negligible. The problem is with the first inner loop. Finding the smallest node. Since I have to do this on a j2ME device, I have to do this to make as little space as possible.
a source to share