Где я могу получить реализацию Java алгоритма Дейкстры?

Я ищу общую реализацию Java алгоритма Дейкстры. Я пробовал кодировать это самостоятельно, но у меня все время возникают проблемы. Если это помогает, я знаю, что график всегда связан. Кто-нибудь знает о такой реализации?

Спасибо!

Ответы

Ответ 1

Это абсолютно бесстыдно, но я закодировал реализацию алгоритма Дейкстры, используя кучи Фибоначчи, и отправил его на свой персональный сайт. Код можно найти здесь:

Я попытался прокомментировать код, чтобы указать, как работает алгоритм, какие предположения он делает и т.д., поэтому, надеюсь, его легко читать и понимать. Дайте мне знать, если что-нибудь об этом я могу вам разъяснить.

Надеюсь, это поможет!

Ответ 2

JGrapht - общая библиотека Java для графиков. Также реализуется алгоритм dijkstra.

Ответ 3

Вы имеете в виду это:

(реализация JAVA может быть найдена по указанной ссылке (см. нижнюю часть ответа)

// initialize d to infinity, π and Q to empty
d = ( ∞ )
π = ()
S = Q = ()

add s to Q
d(s) = 0

while Q is not empty
{
     u = extract-minimum(Q)
     add u to S
     relax-neighbors(u)
}

relax-neighbors(u)
{
     for each vertex v adjacent to u, v not in S
     {
          if d(v) > d(u) + [u,v]    // a shorter distance exists
          {
               d(v) = d(u) + [u,v]
               π(v) = u
               add v to Q
          }
     }
}

extract-minimum(Q)
{
    find the smallest (as defined by d) vertex in Q
    remove it from Q and return it
}

edit: получил это от http://renaud.waldura.com/doc/java/dijkstra/