Алгоритм Dijkstra в Java

У меня есть проблемы с реализацией алгоритма Дейкстры в Java.
Я использую этот (первый) псевдокод: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
Строка 15 вам нужно получить вершину с самым низким расстоянием. Но как я могу сохранить расстояние с соответствующим расстоянием.
Примечание: vertex определяется как целое число.Алгоритм Dijkstra в Java

Мои решения, которые не работают должным образом:

Карта с K = вершины, V = расстояние, задачи: длинный поиск, чтобы получить МИН DIST
SortedMap с K = расстояние, V = вершина, Проблема: почти каждое расстояние определено как Integer.MAX_VALUE

Итак, я ищу быстрый способ сохранить вершину на расстоянии, и должно быть легко получить вершину с минимальным расстоянием.

источник

2015-03-28 fangio

Я не думаю, что и может найти что-то быстрее, чем карта для вас решение – nafas

в качестве альтернативы можно использовать некоторые уже реализованные граф структуры для Java – nafas

Поэтому лучшим решением является на самом деле a SortedMap с K = distance и V = List Integer (= vertex)? – fangio

Попробуйте использовать PriorityQueue. Таким образом, вы можете просто удалить голову, так как она будет иметь минимальное расстояние от всех вершин.

Посмотреть более подробную информацию о PriorityQueue здесь: http://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html

источник

2015-03-28 09:46:55

Priority Queue - плохой выбор для алгоритма Дейкстры, потому что вам обычно нужно изменять затраты на вершины после каждого расслабления. Это означает, что вам нужно будет найти произвольный узел в очереди приоритетов (который не является главой), и он не может быть эффективно выполнен в очереди приоритетов. Его можно решить, не изменяя стоимость каждого узла, но вставляя его несколько раз, но для этого требуется еще больше работы и увеличивается сигнатура памяти алгоритма до «O (| E |)» (в то время как обычно это «O (| V |) ' – amit

@amit У меня была такая же идея, пока я не прочитал здесь http://www3.cs.stonybrook.edu/~rezaul/papers/TR-07-54.pdf, что фактически вставка и удаление элементов может быть лучше чем keyDecrease для большинства графиков. – seteropere

Алгоритм Dijkstra в Java

ответ

Смежные вопросы