7. Задачи, близкие к задаче о кратчайшем пути

В алгоритме Флойда нахождения кратчайшего пути между всеми парами вершин (см. разд. 3 настоящей главы) была использована трехместная операция (8.5). Применение этой операции раз к матрице весов дает «заключительную» матрицу, элементы которой равны длинам кратчайших путей. Эта операция является частным случаем более общей трехместной операции

где функция пути, подлежащая оптимизации, а некоторая общая операция. Операция налагает единственное ограничение в случае ее применения к различным задачам нахождения кратчайших путей в графах. А именно если путь от проходит через промежуточную вершину некоторая характеристика пути, на которой базируется оптимизация, то для должно выполняться условие

Ниже приводится несколько примеров использования этой операции.

7.1. Наиболее надежный путь

В задаче о кратчайшем пути в качестве «длины» пути бралась сумма весов дуг, образующих этот путь. Рассмотрим теперь случай, когда «вес» дуги представляет ее надежность. Надежность пути от составленного из дуг, взятых из множества дается формулой

где надежность дуги т. е. вероятность ее существования в графе (или — в случае физических систем — вероятность того, что она находится в работоспособном состоянии).

Задачу нахождения наиболее надежного пути от можно свести к задаче о кратчайшем пути от взяв в качестве «веса» дуги величину Прологарифмировав обе части соотношения (8.10), получим

Отсюда видно, что кратчайший путь от с матрицей весов будет в то же время и наиболее надежным путем с матрицей: а надежность этого пути равна антилогарифму его длины.

При другой формулировке задачи о наиболее надежном пути возможно непосредственное использование трехместной операции; а именно операция вводится с помощью соотношения

В качестве начальной -матрицы берется матрица надежностей дуг, причем нулевые элементы указывают на отсутствие соответствующих дуг. Такая формулировка позволяет, очевидно, найти наиболее надежные пути между всеми парами вершин.