5.8. АЛГОРИТМ НАХОЖДЕНИЯ КРАТЧАЙШЕГО ПУТИ
Для вычисления кратчайшего пути воспользуемся вторым замкнутым полукольцом из примера 5.9, а именно множеством неотрицательных вещественных чисел вместе с 
Напомним, что аддитивной операцией является MIN, а мультипликативной — сложение вещественных чисел. Иными словами, рассмотрим структуру 
В примере 5.10 отмечалось, что 
для всех 
так что снова можно обойтись без операции в строке 5 алгоритма 5.5, заменив эту строку на
Неформально можно сказать, что оператор (5.5) означает, что кратчайшим путем из 
не проходящим через узлы, индексы которых больше 
будет более короткий из следующих двух путей:
1) кратчайшего пути, не проходящего через узлы, индексы которых больше 
и
2) кратчайшего пути из 
и затем в 
не проходящего через другие узлы, индексы которых больше 
Чтобы превратить алгоритм 5.5 в алгоритм нахождения кратчайшего пути, зададим 
как стоимость ребра 
если
Рис. 5.20. Вычисление кратчайшего пути.
в противном случае. Затем заменим строку 5 оператором (5.5), и по теореме 5.5 значение с 
выданное алгоритмом 5.5, будет наименьшей стоимостью (т. е. суммой стоимостей ребер) пути из всех путей между 
примут значения, как в таблицах на рис. 5.20. Например, 
