L'algorithme de Dijkstra le plus rapide pour j2ME

Question

Quelqu'un peut-il m'aider à accélérer l'implémentation j2ME de l'algorithme de Dijkstra? J'ai deux boucles, l'une dans l'autre. Comme cette

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. 
    } 
} 

J'ai presque 23000 noeuds et arêtes les reliant 50000 ... La boucle interne exécute en moyenne 169330131 fois après toutes les améliorations mentionnées ci-dessous. Cela prend 5 minutes pour compléter sur mon mobile w910i et plus de minutes sur mon émulateur. Cela semble trop pour moi. Des suggestions d'amélioration? J'ai les améliorations suivantes déjà implémentées.

1. Utilisation d'un tableau à la place du vecteur.
2. Assurez-vous que la boucle interne ne prend pas en compte les nœuds visités. Tous mes nœuds visités sont à la fin du tableau et le nœud I connaît le nombre. Donc, je peux facilement les ignorer complètement.

Answer 1

Quelque chose ne va pas avec votre implémentation. Sa complexité est O (E + V * log2 (V)).

Cela signifie 50000 + 23000 * ~ 15 = 400 000 itérations.

Votre complexité actuelle est presque O (V^2).

Answer 2

Je pense que votre algorithme dans la question est faux. La boucle intérieure devrait se pencher sur chaque voisin unvisited de l'élément dans la boucle extérieure:

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

Comparez avec le 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

j'ai parlé cet algorithme. J'ai trouvé un algorithme plus simple à un autre endroit. S'il vous plaît noter que si je devais implémenter celui dans Wikipedia, il y a deux boucles internes.

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. 

La deuxième boucle interne est plus petite. Il peut exécuter un maximum de 4-5 car il y a au plus 5 arêtes pour chaque nœud. Le nombre de nœuds ayant plus de 2 arêtes est de 1000 sur 23 000 nœuds au total. Ainsi, le temps d'exécution de la boucle interne est négligeable. La première boucle interne est le problème. Trouver le plus petit noeud. Comme je dois l'exécuter sur un appareil j2ME, je dois le faire pour prendre le moins d'espace possible.