Глава VI Пути в сетях

Напомним, что ориентированный взвешенный граф G=(V,E,c) называется сетью. Сеть может быть представлена в компьютере матрицей весов дуг, массивами смежностей СЛЕД или ПРЕДШ, или списками СЛЕД[v] или ПРЕДШ[v]. При этом записи в спи­сках смежностей состоят из грех компонент: поля имени узла, поля веса соответствующей дуги и поля ссылки на следующую запись.

Пусть р: v=v₀,v₁,...,v_k=w — путь в сети G от узла v до узла w (v-w-путь); положим

c(p)⁼c(v₀, v₁)+...+c(v_k-1, v_k).

Число с(р) назовем длиной пути р. Наименьшую из длин v-w-путей назовем расстоянием от v до w, а тот v-w-путь, длина которого равна расстоянию от v до w, — кратчайшим v-w-путем. Ясно, что расстояние от v до w может отличаться от расстояния от w до V.

Задача о кратчайшем пути (ЗКП) между фиксированными узлами: в заданной сети G с двумя выделенными узлами s и t найти кратчайший s-t-путь.

Отметим сразу, что ЗКП можно рассматривать и в неориенти­рованных взвешенных графах, заменив каждое ребро {v,w} графа двумя дугами (v,w) и (w,v) и считая, что c(v,w)=c(w,v)=c({v,w}).

Далее, если в невзвешенном графе положить вес каждого реб­ра равным единице, то получим данное ранее определение длины пути (см.гл.2 и гл.4) как числа ребер. С этой точки зрения рас­смотренная в гл.4 задача построения кратчайшего по числу ребер пути есть частный случай сформулированной только что задачи.

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

Можно дать много практических интерпретаций ЗКП. Одна из таких была дана в главе первой, где была рассмотрена задача на­хождения самого короткого пути между городами. Другая, менее очевидная ситуация возникает в задаче выбора самого надежного пути передачи информации в некоторой информационной сети.

Пусть имеется информационная сеть, связывающая n пунктов связи, и для каждого канала (v,w) передачи информации от пунк­та связи v к пункту w известна вероятность P(v,w) его безаварий­ной работы. Предположим, что аварии каналов не зависят друг от друга. Тогда вероятность исправности пути q: s=v₀,v₁,...,v_k=t пе­редачи информации от s до t равна

P(q) = П{P(v_i-1,v₁) : i=l,2,...,k}.

Самым надежным путем передачи информации от s к t естест­венно считать тот путь q, для которого значение P(q) максималь­но.

Рассмотрим сеть G*. узлы которой соответствуют пунктам связи, а дуги — каналам передачи информации, и для дуги (v,w) полагаем c(v,w) = -logP(v,w). Пусть в этой сети для узлов s и t решена ЗКП, то есть найден кратчайший s-t-путь q: s=v_o,v₁,…,v_k=t. Иначе говоря, c(q) = ∑{c(v_i-1,v₁):i=l,2,...,k}→min среди всех s-t-путей, то есть ∑{-logP(v_i-1,v₁):i=l,2,...,k}→min.

Тогда log(П{P(v_i-1,v₁):i=l,2,...,k})→max. Отсюда следует, что для кратчайшего s-t-пути q вероятность правильного прохожде­ния сигнала максимальна среди всех s-t-путей. Таким образом, кратчайший s-t-путь в сети G* определяет самый надежный путь передачи информации в информационной сети.