интерпретируя Дейкстры Алгоритм

Question

Я понимаю, как найти кратчайший путь от начала до конца, как это описывается алгоритмом Дейкстры, что я не понимаю, это интерпретация. Здесь, из графика на картинке, порядок, добавленный в мой известный набор от А до Е, равен A,C,B,D,F,H,G,E, чего я не получаю, как получить путь от А до Е, как показано на рисунке (математический аспект)

Answer 1

Каждый узел имеет родительский узел. Когда вы достигнете 'E', вы просто посмотрите на его родителя и так далее, пока не найдете 'A'. Таким образом, вы найдете список в обратном порядке. Переверните список, чтобы найти путь от 'A' до 'E'.

Ваш родительский список будет 'E' 'G' 'H' 'F' 'B' 'A', если вы добавите его в порядок.

Примечание: «родительский узел» является узлом указано в колонке «пути» стола

Answer 2

Рассмотрим минимальную очередь приоритета, содержащий пути должны быть перемещены, где приоритет по пути на очереди является стоимость перемещения краев на пути от корня до и включая это ребро. На каждом шаге алгоритма выходим самый низкий путь из очереди и, рассматривая каждый из его краев инцидента, расширяем путь с этим краем инцидента и вставляем новый путь обратно в очередь в порядке приоритета. Повторяйте до тех пор, пока первый путь не достигнет места назначения.

Например:

1. Начать с пустой очереди <>
2. Затем, начиная от корня A, поместить все падающие края (A->B, A->C и A->D с затратами 2, 1 и 4 соответственно) в очередь и порядок по приоритету: <(A->C,1),(A->B,2),(A->D,4)>
3. Направьте путь с минимальным приоритетом A->C с передней стороны очереди, а затем рассмотрите края, инцидентные концу пути C и раздвинуть эти пути обратно на очередь (поддержание порядка приоритета): <(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)>
4. Repeat, выскакивает минимальный приоритет путь A->B от расширения и пути с падающими краями <(A->D,4),(A->B->F,4),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
5. Продолжайте идти ... поп A->D и толчок больше падающих края: <(A->B->F,4),(A->D->C,6),(A->B->C,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
6. поп A->B->F и самокаты больше падающих края: <(A->D->C,6),(A->B->C,7),(A->B->F->H,7),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
7. поп A->D->C - однако, мы уже достигли C с более низкой стоимостью пути так может его игнорировать.
8. pop A->B->C и игнорировать его.
9. поп A->B->F->H и толкают больше падающих края: <(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)>
10. поп A->B->F->H и толкают больше падающих края: <(A->B->F->H->G->F,10),(A->C->A,10),(A->B->F->H->G->E,11),(A->B->E,12),(A->C->E,12)>
11. поп A->B->F->H->G->F и игнорировать его.
12. pop A->C->A и игнорировать его.
13. pop A->B->F->H->G->E, и мы достигли цели (со стоимостью 11)!

Answer 3

Начиная с начального узла, вычисление суммарного веса производится при перемещении графика к доступным узлам. Совокупный вес от одного узла к смежному узлу сравнивается с любыми предыдущими результатами (т. Е. Возможными обходами этого узла). В качестве «победителя» выбирается маршрут с наименьшим суммарным весом. Процесс повторяется до тех пор, пока путь от начала до конечного узла не будет найден и не оценен как самый низкий совокупный вес.

Таким образом, в данном примере вы показали:

• ACE = 12
• ADCE = 17
• АВЕ = 12

ABFHGE это единственный путь влево (в пределах ориентированного графа) с наименьшим общим весом 11 (а также самым длинным путем) от начала до конца.

Как вы рассчитываете с самого начала, некоторые пути могут казаться изначально короче (AC), но по мере того, как алгоритм прогрессирует, эти варианты игнорируются по мере изучения всех путей от A до E.