Я понимаю, как найти кратчайший путь от начала до конца, как объясняется алгоритмом Дейкстры, я не понимаю, это интерпретация. Здесь, из графика на картинке, порядок, добавленный в мой известный набор от А до Е, A,C,B,D,F,H,G,E, что я не получаю, как получить путь от А до Е, как показано на рисунке (математический аспект)
Каждый node имеет родительский node. Когда вы достигнете 'E', вы просто посмотрите на его родителя и так далее, пока не найдете 'A'. Таким образом, вы найдете список в обратном порядке. Переверните список, чтобы найти путь от 'A' до 'E'.
Ваш родительский список будет 'E' 'G' 'H' 'F' 'B' 'A', если вы добавите его в порядок.
ПРИМЕЧАНИЕ. "parent node" - это node, указанный в столбце "путь" таблицы
Рассмотрим очередь с минимальным приоритетом, содержащую пройденные пути, где приоритет пути в очереди - это затраты на перемещение ребер в пути от корня до и включая этот край. На каждом шаге алгоритма выходим самый низкий путь из очереди и, рассматривая каждый из его краев инцидента, расширяем путь с этим краем инцидента и вставляем новый путь обратно в очередь в порядке приоритета. Повторяйте до тех пор, пока первый путь не достигнет пункта назначения.
Например:
<>A, поместите все краёв инцидента (A->B, A->C и A->D с затратами 2, 1 и 4 соответственно) в очередь и порядок по приоритету: <(A->C,1),(A->B,2),(A->D,4)>A->C с передней части очереди, а затем рассмотрите края, инцидентные концу пути C, и переместите эти пути обратно в очередь (поддерживая порядок приоритетов): <(A->B,2),(A->D,4),(A->C->A,10),(A->C->E,12)>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)>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)>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)>A->D->C - однако мы уже достигли C с более низким уровнем затрат, поэтому можем игнорировать его.A->B->C и игнорировать его.A->B->F->H и нажмите больше краев инцидентов: <(A->B->F->H->G,8),(A->C->A,10),(A->B->E,12),(A->C->E,12)>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)>A->B->F->H->G->F и игнорировать его.A->C->A и игнорировать его.A->B->F->H->G->E, и мы достигли цели (со стоимостью 11)!Начиная с начала node, вычисление совокупного веса производится при перемещении графика к доступным узлам. Совокупный вес от одного node до смежного node сравнивается с любыми предыдущими результатами (т.е. Возможными обходами к этому node). В качестве "победителя" выбирается маршрут с наименьшим суммарным весом. Процесс повторяется до тех пор, пока не будет найден и оценен путь от начала до терминала node как наименьший совокупный вес.
Итак, в примере, который вы показали:
ABFHGE - единственный путь слева (внутри ориентированного графика) с наименьшим общим весом 11 (а также самым длинным путем) от начала до конца.
Как вы рассчитываете с самого начала, некоторые пути могут казаться первоначально короче (AC), но по мере того, как алгоритм прогрессирует, эти варианты игнорируются по мере изучения всех путей от A до E.