Ч МИН
тот путь занимает 7 минут. А может, существует путь, который займет меньше времени? Алгоритм Дейкстры состоит из четырех шагов:
Найти узел с наименьшей стоимостью (то есть узел, до которого можно добраться за минимальное время).
Обновить стоимости соседей этого узла (вскоре я объясню, что имеется в виду).
Повторять, пока это не будет сделано для всех узлов графа.
Вычислить итоговый путь.
Ш аг 1: найти узел с наименьшей стоимостью. Вы стоите в самом начале и думаете, куда направиться: к узлу А или к узлу В. Сколько времени понадобится, чтобы добраться до каждого из этих узлов?
До узла А вы будете добираться 6 минут, а до узла В — 2 минуты. Что касается остальных узлов, мы о них пока ничего не знаем. ьремл
ПЕРЕХОДА
Т
ак как время достижения конечного узла остается не- узел к узлу известным, мы считаем, что оно бесконечно (вскоре вы увидите почему.) Узел В — ближайший... он находится всего в 2 минутах.
Шаг 2: вычислить, сколько времени потребуется для того, чтобы добраться до всех соседей В при переходе по ребру из В.
Do'stlaringiz bilan baham: |