가장 빠른 Dijkstra 알고리즘에 대한 j2ME

Question

아무도 내가 Dijkstra 알고리즘의 J2ME 구현을 빠르게 할 수 있습니까? 나는 두 개의 고리를 가지고 있는데 하나는 다른 고리 안에있다. 이

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

같이 내가 그들을 연결하는 거의 23000 노드와 50000 가장자리가 ... 내부 루프는 아래에 언급 된 모든 개선 후 169,330,131 배의 평균을 실행합니다. 이것은 내 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에서 구현해야한다면 두 개의 내부 루프가 있다는 점에 유의하십시오.

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. 

두 번째 내부 루프가 더 작습니다. 각 노드에 대해 최대 5 개의 에지가 있으므로 최대 4-5 개까지 실행할 수 있습니다. 에지가 2 개 이상인 노드의 수는 총 23000 개의 노드 중 1000 개입니다. 따라서 내부 루프의 실행 시간은 무시해도 좋습니다. 첫 번째 내부 루프가 문제입니다. 가장 작은 노드 찾기. j2ME 장치에서이 작업을 실행해야하므로 최대한 공간을 적게 차지해야합니다.