Кратчайший путь
Кратчайший путь — это маршрут между двумя заданными вершинами графа, у которого минимальна суммарная длина или стоимость. В зависимости от задачи нужно найти сам путь, его длину или стоимость.
Чтобы сравнить маршруты, сначала определяют длину маршрута — сумму весов всех его рёбер. В невзвешенном графе каждое ребро обычно считают имеющим вес \(1\), поэтому длина пути равна числу переходов между вершинами. Если между двумя вершинами существует несколько путей, кратчайшим называют путь с наименьшей суммой.
Здесь \(P\) — путь, \(e_i\) — его рёбра, \(w(e_i)\) — вес очередного ребра, а \(k\) — число рёбер. Расстояние между вершинами — это длина кратчайшего пути между ними. Если пути нет, расстояние считают бесконечным или говорят, что вершины недостижимы.
Пусть из вершины \(A\) в \(D\) можно пройти по маршрутам \(A\to B\to D\) со стоимостью \(3+4=7\) и \(A\to C\to D\) со стоимостью \(2+6=8\). Кратчайший путь — \(A\to B\to D\), его стоимость равна \(7\).
Расстояние между вершинами — это числовая длина кратчайшего пути, а не сам маршрут. В графе могут существовать несколько разных кратчайших путей одинаковой длины. Для поиска таких путей применяют алгоритмы, например алгоритм Дейкстры; результаты для многих пар вершин можно записать в таблице кратчайших расстояний.
У маршрута \(A\to B\to C\) веса рёбер равны \(5\) и \(2\), а у маршрута \(A\to D\to C\) — \(3\) и \(6\). Каков кратчайший путь из \(A\) в \(C\)?
Главное
- Кратчайший путь имеет минимальную сумму весов рёбер между заданными вершинами.
- В невзвешенном графе сравнивают количество рёбер.
- Расстояние — это длина кратчайшего пути; сам маршрут и его длина — разные понятия.