Свойства кратчайшего пути

Опубликовано: 22 Сентября, 2022

Задача о кратчайшем пути — это задача о нахождении пути между двумя вершинами (или узлами) в графе, при котором сумма весов составляющих его ребер минимальна. Кратчайший путь между любыми двумя узлами графа можно найти с помощью многих алгоритмов, таких как алгоритм Дейкстры, алгоритм Беллмана-Форда, алгоритм Флойда-Уоршелла. Существуют некоторые свойства поиска кратчайших путей, на основании которых работает алгоритм поиска кратчайшего пути:

  1. Оптимальное свойство основания
    • Все подпути кратчайшего пути также должны быть кратчайшими путями.
    • Если существует кратчайшая длина пути между двумя узлами 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.

    График G

  2. Неравенство треугольника
    • Позволять d(a, b) — длина кратчайшего пути от a до b в графе G 1 . Затем,
      • d(a, b) ≤ d(a, x) + d(x, b)

    График G 1