Самый быстрый алгоритм Дейкстры для j2ME

Question

Может ли кто-нибудь помочь мне быстрее реализовать j2ME алгоритм Dijkstra? У меня две петли, одна внутри. Как это

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 ребра, соединяющие их ... Внутренний цикл выполняется в среднем 169330131 раз после всех улучшений, указанных ниже. Это займет 5 минут, чтобы завершить мой w910i мобильный и более чем на минут на моем эмуляторе. Это слишком много для меня. Любые предложения по улучшению? У меня уже есть следующие улучшения.

1. Использование массива вместо вектора.
2. Убедитесь, что внутренний цикл не учитывает посещенные узлы. Все мои посещенные узлы находятся в конце массива, и я узел знаю счет. Поэтому я могу легко пропустить их вообще.

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

Я передал этот алгоритм. Я нашел более простой алгоритм в другом месте. Обратите внимание, что если бы мне пришлось внедрить тот, который был в Википедии, есть два внутренних цикла.

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. 

Второй внутренний контур меньше. Он может выполнять максимум 4-5, поскольку для каждого узла должно быть не более 5 ребер. Число узлов, имеющих более 2 ребер, составляет 1000 из 23000 общих узлов. Таким образом, время выполнения для внутреннего цикла пренебрежимо мало. Проблема заключается в первом внутреннем цикле. Поиск наименьшего узла. Поскольку я должен выполнить это на устройстве j2ME, я должен сделать это, чтобы взять как можно меньше места.