Где я могу получить реализацию 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/
Ответ 4
Хорошие ресурсы из университетов
Также vogella сделала хорошую реализацию на http://www.vogella.com/articles/JavaAlgorithmsDijkstra/article.html