Алгоритм Форда-Беллмана нахождения минимального пути в нагруженном ориентированном графе

1. 
   Составляем таблицу , i=1,…,n, k=0,…,n-1. Если , то пути из v_нач в v_кон нет. Конец алгоритма.
   
2. 
   Если то это число выражает длину любого минимального пути из v_нач в v_кон. Найдем минимальное k₁1, при котором . По определению получим, что k₁- минимальное число дуг в пути среди всех минимальных путей из v_нач в v_кон.
   
3. 
   Затем определяем номера i₂,…, такие, что
   

то есть, восстанавливаем по составленной таблице и матрице стоимости искомый минимальный путь из v_нач в v_кон.