Page 158 - Bkhargava_-_Grokaem_algoritmy

Терминология 157

На всякий случай повторим: алгоритм Дейкстры состоит из четырех шагов:

1. Найти узел с наименьшей стоимостью (то есть узел, до которого можно
добраться за минимальное время).

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

3. Повторять, пока это не будет сделано для всех узлов графа.

4. Вычислить итоговый путь (об этом в следующем разделе!).

Терминология

Я хочу привести еще несколько примеров применения алгоритма Дейкстры.
Но сначала стоит немного разобраться с терминологией.

Когда вы работаете с алгоритмом Дейкстры, с каждым ребром графа свя­
зывается число, называемое весом.

Граф с весами называется взвешенным графом. Граф без весов называется
невзвешенным графом.

ЬJ6ЕШЕННЬIК ГРАФ HE6J6ElllEHHЬIK ГРАФ

www.trk.kg