Алгоритм Форда (случай общей матрицы весов)
Алгоритм Дейкстры применим лишь в том случае, когда 
для всех i и j. Однако если матрица С является матрицей стоимостей, то дуги, приносящие доход, должны иметь отрицательные «стоимости».
Описание алгоритма Форда:
Пусть 
- пометка вершины 
в конце (k+1)–й итерации.
Шаг 1. Положить S=Г(s), k=1, 
, 
для всех 
и 
для всех остальных xi.
Шаг 2. Для каждой вершины 
(
) изменить ее пометку следующим образом:
,
где 
(множество 
содержит те вершины, для которых текущие кратчайшие пути из s состоят из k дуг и для которых существуют дуги к вершине xi.). Для вершин 
положим 
.
Шаг 3.
1. Если 
и для всех xi, то получен оптимальный ответ и пометки равны длинам кратчайших путей.
2. Если 
и 
для некоторой вершины xi, то перейти к шагу 4.
3. Если 
и для некоторой вершины xi, то в графе существует цикл отрицательного веса и задача не имеет решения.
Шаг 4. Обновить множество S следующим образом:
.
Шаг 4. Положить 
и перейти к шагу 2.
Также можно привести общую матрицу весов к неотрицательной, увеличив вес каждого ребра на величину 
и найти кратчайшие пути между вершиной s и всеми другими вершинами с помощью алгоритма Дейкстры.