Алгоритъмът на Dijkstra не генерира най-кратък път? - алгоритъм, теория на графиките, най-кратък път, дидхстра

Работя по най-краткия пътизползвайки алгоритъм на Dijkstra.Аз имам проблеми, защото алгоритъмът трябва да осигури най-кратък път, но след като се изпълнява алгоритъм получавам shorted път на ръка.Това ли е само един страничен продукт на този алгоритъм?

Пътят, който се опитвам да генерирам, е от -> z

Ето пътя, който получавам от прилагането на алгоритъма, като вземам най-краткия скок на разстояние от всеки връх, който посещавам:

  2    4    2    2    1    2    1    1    8      = 23
a -> d -> g -> k -> r -> n -> q -> p -> t -> z

Това ми е объркващо, защото ако направя този път:

  4    2    2    2    2    2    2     = 16
a -> c -> f -> i -> m -> p -> s -> z

Получавам разстояние, което е 5 по-малко от разстоянието, генерирано от алгоритъма.

Не съм ли някъде някъде?

Отговори:

Изглежда, че не разбирате по какъв начин е Dijkstraалгоритъм работи. Вместо да вземете ръба с най-малко тегло на всеки възел, винаги трябва да имате предвид общото разстояние от началото (възел $ a $). Поддържате купчина от всички възможни пътища, които започват да се разглеждат като начален възел без краища и се разширяват, като добавите всички пътища с всеки изходящ край на възел, добавен към пътя, който разглеждате понастоящем на всяка стъпка.

Това е съвсем малко думи, които се опитват да обобщят къде се объркахте. Предлагам да прочетете отново как работи алгоритъмът на Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm