最も速いDijkstraアルゴリズムfor j2ME

Question

誰でも私がDijkstraアルゴリズムのj2ME実装を高速化するのを助けることができますか？私は2つのループを持っています。私はほとんど23000ノードとそれらを接続50000のエッジを有するこの

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

よう...インナーループは、以下に言及される全ての改良後169330131回の平均を実行します。これは私のw910i携帯電話では5分、エミュレータでは数分以上かかる。これは私のためにあまりにも多く見えます。改善のための提案はありますか？私はすでに以下の改善が行われています。

1. ベクトルの代わりに配列を使用します。
2. 内部ループが訪問先ノードを考慮していないことを確認してください。訪問したすべてのノードは配列の最後にあり、Iノードはカウントを知っています。だから、私は簡単にそれらをすべてスキップすることができます。

Answer 1

実装に問題があります。複雑さはO（E + V * log2（V））です。

これは、50000 + 23000 *〜15 = 400 000回の繰り返しを意味します。

あなたの現在の複雑さはほぼO（V^2）です。

Answer 2

私はあなたのアルゴリズムが問題だと思います。内側のループは、外側のループ内の項目の各未訪問の隣人を見てする必要があります。

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

は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

私はこのアルゴリズムを言及しました。もっと単純なアルゴリズムが見つかった。 Wikipediaで実装しなければならない場合、内部ループは2つあります。

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. 

2番目の内側ループが小さくなります。各ノードに対して最大5つのエッジが存在するため、最大4〜5回実行される可能性があります。エッジが2つ以上あるノードの数は、23000個のノードのうち1000個です。したがって、内部ループの実行時間は無視できます。最初の内側ループが問題です。最小のノードを見つける。これをj2MEデバイスで実行する必要があるため、できるだけスペースを少なくする必要があります。