Действительно только одно. Пока нет математической постановки задачи, нет смысла говорить об алгоритме.
В постановке самого общего вида речь идёт о взвешенном орграфе с произвольными весами, но без контуров отрицательного веса. Для этого случая алгоритм Форда-Беллмана (вектор расстояний от источника до всех вершин графа, выч. сложность O(nm)), алгоритм Флойда (матрица расстояний между всеми парами вершин, выч. сложность
), алгоритм Йена (первые k кратчайших путей между парой фиксированных вершин, выч. сложность
).
Если на том же графе веса неотрицательные, то алгоритм Дейкстры (вектор расстояний за
), алгоритм Йена для первых k кратчайших путей за
Если орграф бесконтурный, то после правильной нумерации вектор расстояний за O(m).
Если граф неориентированный, то любое ребро отрицательного веса при расщеплении на пару противоположно направленных дуг образует контур отрицательного веса, к такому графу Флойд и Форд-Беллман уже не применимы. Если под кратчайшим путём понимается путь, у которого все вершины различны, то кратчайшие пути на таком графе находятся за экспоненциальное время.
Если граф неориентированный с неотрицательными весами, то направление не имеет значения, всё тот же вектор расстояний, который можно найти алгоритмом Дейкстры.
Если ориентированный без контуров отр. веса - тогда Флойд.
Если неориентированный с отрицат. весами - алгоритм с возвратом (бэктрекинг).