Свойства кратчайшего пути
Опубликовано: 22 Сентября, 2022
Задача о кратчайшем пути — это задача о нахождении пути между двумя вершинами (или узлами) в графе, при котором сумма весов составляющих его ребер минимальна. Кратчайший путь между любыми двумя узлами графа можно найти с помощью многих алгоритмов, таких как алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм Флойда-Уоршелла. Существуют некоторые свойства поиска кратчайших путей, на основании которых работает алгоритм поиска кратчайшего пути:
- Оптимальное свойство основания
- Все подпути кратчайшего пути также должны быть кратчайшими путями.
- Если существует кратчайшая длина пути между двумя узлами U и V , то жадный выбор ребра с минимальной длиной между V и S даст кратчайшую длину пути между U и S .
- Все перечисленные выше алгоритмы работают на основе этого свойства.
- Например, пусть P1 — подпуть из (X → Y) кратчайшего пути (S →X →Y → V) графа G. И пусть P2 — любой другой путь (X → Y) в графе G. Тогда стоимость P 1 должна быть меньше или равна стоимости P 2 . В противном случае путь (S → X → Y → V) не будет кратчайшим путем между узлами S и V.
- Неравенство треугольника
- Позволять d(a, b) — длина кратчайшего пути от a до b в графе G 1 . Затем,
- d(a, b) ≤ d(a, x) + d(x, b)
- Позволять d(a, b) — длина кратчайшего пути от a до b в графе G 1 . Затем,