- кратчайший путь
- Кратчайший путь в графе — это путь минимальной длины между двумя вершинами. Длина пути определяется суммой весов рёбер.
- алгоритм Дейкстры
- Алгоритм Дейкстры находит кратчайшие пути от одной вершины до всех остальных в графе с неотрицательными весами рёбер.
- алгоритм Флойда — Уоршелла
- Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми парами вершин в графе с произвольными весами рёбер.
- матрица кратчайших путей
- Матрица кратчайших путей — это квадратная матрица, где элемент на пересечении строки и столбца показывает кратчайший путь между соответствующими вершинами.
- взвешенный граф
- Взвешенный граф — это граф, в котором каждому ребру присвоен вес, отражающий, например, расстояние или стоимость.
- неотрицательные веса рёбер
- Неотрицательные веса рёбер — это веса, которые не меньше нуля, что позволяет использовать алгоритм Дейкстры.
- алгоритм OAG
- Алгоритм поиска кратчайших путей в ориентированном ациклическом графе (OAG) использует динамическое программирование.
- неединственность кратчайшего пути
- В графе кратчайший путь может быть не единственным, если есть несколько путей с одинаковой минимальной длиной.
- алгоритм Беллмана — Форда
- Алгоритм Беллмана — Форда находит кратчайшие пути в графе с отрицательными весами рёбер, но требует, чтобы не было отрицательных циклов.
- отрицательный цикл
- Отрицательный цикл — это цикл в графе, в котором сумма весов рёбер отрицательна, что делает бессмысленным понятие кратчайшего пути.
- алгоритм Джонсона
- Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин в графе с произвольными весами рёбер, включая отрицательные.