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

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

• • алгоритм Дейкстры (алгоритм поиска кратчайших путей от заданой вершины)
  • алгоритм Флойда (алгоритм поиска длин всех кратчайших путей в графе)
  • алгоритм Данцига