Вычисление кратчайшего пути для всех пар

В некоторых приложениях требуется быстро найти кратчайший путь между всеми парами узлов сети. Если необходимо вычислять большую часть из всех возможных N2 путей, то проще заранее найти все возможные кратчайшие пути, а не высчитывать их каждый по мере надобности.

Можно сохранить кратчайшие пути в двумерных массивах Dists и inLinks. В ячейке Dists[i,j] содержится кратчайшее расстояние от узла i до узла j, а в ячейке InLinks[i,j] — связь, которая ведет к узлу j в кратчайшем пути от узла i до узла j. Эти значения подобны значениям Dist и InLink в классе узла из предыдущих алгоритмов.

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

Другой метод вычисления всех кратчайших путей последовательно строит пути через сеть, используя все более увеличивающееся количество узлов. Сначала алгоритм отыскивает все кратчайшие пути, которые обходят только первый узел плюс конечные узлы пути. Другими словами, для узлов j и k алгоритм находит кратчайший путь между этими узлами, который использует только узел с номером 1 и узлы j и k, если такой путь существует.

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

Кратчайший путь от узла j к узлу k, использующий только первые i узлов будет включать узел i только в случае выполнения неравенства Dist[j,k]Dist[j,i]+Dist[i,k]. В противном случае кратчайшим будет предыдущий кратчайший путь, использующий только первые i — 1 узлов. Это означает, что когда алгоритм рассматривает узел i, надо проверить только это условие. Если оно выполняется, алгоритм обновляет кратчайший путь от узла j к узлу k. Иначе старый кратчайший путь между этими двумя узлами все еще является таковым.

Применение алгоритмов поиска кратчайшего пути

Задача о пожарных депо

Предположим, что имеется карта города, которая показывает расположение всех пожарных депо. Необходимо определить для каждой точки города ближайшее к ней депо. Для решения задачи можно попытаться вычислить деревья кратчайших путей с корнями в каждом узле сети, чтобы найти, какое из пожарных депо расположено ближе всего к тому или иному узлу. Или создать дерево кратчайших путей, с корнями в каждом из пожарных депо и сохранить расстояния от каждого пожарного депо до каждого узла сети. Но есть и более эффективный метод.

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

Максимальный поток

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

На рис. 39 изображена небольшая нагруженная сеть. Числа рядом с ребрами — это не стоимость связи, а ее пропускная способность. В данном примере максимальный поток, равный 4, получается, если две единицы потока направляются по пути А, В, Е, F и еще две- по пути А, С, D, F.

Рис. 39. Нагруженная сеть

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

Чтобы найти способы увеличения полного потока, алгоритм исследует разностную пропускную способность связи. Разностная пропускная способность связи между узлами i и j равна максимальному дополнительному сетевому потоку, который можно направить из узла i в узел j, используя связь между i и j и связь между j и i. Этот сетевой поток может включать дополнительный поток через связь i-j, если есть резерв пропускной способности. Он может также исключать часть из потока j-i, если по данной связи идет поток.

Например, предположим, что в сети, соединяющей узлы А и С на рис. 39, существует поток, равный 2. Поскольку пропускная способность этой связи равна 3, к ней можно добавить единицу потока, поэтому ее разностная пропускная способность равна 1. Хотя сеть, изображенная на рис. 39, не имеет связи С-А, разностная пропускная способность для этой связи существует. В данном примере, так как по связи С-А идет поток, равный 2, то можно удалить до двух единиц данного потока. Это увеличит сетевой поток от узла С к узлу А на 2, поэтому разностная пропускная способность связи С-А равна 2.

Сеть, состоящая из всех связей с положительной разностной пропускной способностью, называется разностной сетью. Ha рис. 40 изображена сеть с рис. 39, каждой связи в которой присвоен поток. Для каждой связи первое число равно потоку через связь, а второе — ее пропускной способности. Метка 1/2, например, означает, что связь проводит поток 1 и имеет пропускную способность 2. Связи, несущие потоки больше нуля, нарисованы жирными линиями.

Рис. 40. Сетевые потоки

На рис. 41 изображена разностная сеть, соответствующая потокам, приведенным на рис. 40. Показаны только те связи, которые действительно могут иметь разностную пропускную способность. Например, между узлами А и D не нарисовано ни одной связи. Исходная сеть не имеет связи A-D или связи D-A, поэтому эти связи всегда будут иметь нулевую разностную пропускную способность.

Рис. 41. Разностная сеть

Важное свойство разностных сетей заключается в том, что любой путь, использующий связи с разностной пропускной способностью больше нуля, который соединяет источник со стоком, показывает способ увеличения потока сети. Этот путь называется расширяющим путем. На рис. 42 изображена разностная сеть с рис. 41, расширяющий путь в ней выделен жирными линиями.

Рис. 42. Расширяющийся путь через разностную сеть

Чтобы улучшить решение с помощью расширяющего пути, необходимо найти наименьшую разностную пропускную способность на этом пути. Затем следует скорректировать потоки в пути в соответствии с данной величиной. На рис. 42, например, наименьшая разностная пропускная способность любого ребра на расширяющем пути равна 2. Чтобы обновить потоки в сети, следует прибавить поток 2 к любой связи пути i-j, а из всех обратных им связей j-i вычесть поток 2.

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

Чтобы изменить разностную сеть в данном примере, необходимо проследовать по расширяющему пути и вычитать 2 из разностной пропускной способности любого ребра i-j на этом пути, и добавлять 2 к разностной пропускной способности соответствующего ребра j-i. На рис. 43 изображена измененная разностная сеть для данного примера.

Рис. 43. Измененная разностная сеть

Если нельзя больше найти ни одного расширяющего пути, то можно использовать разностную сеть для вычисления потоков в исходной сети. Для каждой связи между узлами i и j, если разностный поток между узлами i и j меньше, чем пропускная способность связи, поток должен равняться пропускной способности минус разностный поток. В противном случае поток должен быть равен нулю.

Например, на рис. 43 разностный поток от узла А к узлу С равен 1, а пропускная способность связи А-С равна 3. Поскольку 1 меньше 3, поток через узел будет равен 3-1=2. На рис. 44 показаны сетевые потоки, соответствующие разностной сети на рис. 43.

Рис. 44. Максимальные потоки

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

Статьи к прочтению:

Примеры задач динамического программирования: поиск кратчайшего пути

Похожие статьи: