Алгоритмы поиска кратчайших путей

Каждой дуге (х, у) исходного графа G поставим в соответствие число ах,у. Если в графе отсутствует некоторая дуга (х, у), положим ах,у =∞. Будем называть число ах,у длиной дуги (х, у), хотя ах,у можно также интерпретировать как соответствующие затраты или соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг, составляющих этот путь.
Для любых двух вершин s и t графа G могут существовать несколько путей, соединяющих вершину s с вершиной t. В теории графов рассматривается задача, цель которой определить такой путь, ведущий из вершины s в вершину t, который имеет минимально возможную длину. Этот путь называется кратчайшим путем между вершинами s и t.

Читайте также  Алгоритм Литтла - Пример 1

Существует несколько методов поиска кратчайших путей в графе:

    • алгоритм Дейкстры (алгоритм поиска кратчайших путей от заданой вершины)
    • алгоритм Флойда (алгоритм поиска длин всех кратчайших путей в графе)
    • алгоритм Данцига
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (Пока оценок нет)
Загрузка...