for k:=1 to nn do

for i:=1 to nn do

for j:=1 to nn do

a[i,j]:=a[i,j] or a[i,k] and a[k,j];

Краткость говорит здесь сама за себя. В результате выполнения трех вложенных циклов (то есть мы имеем алгоритм, работающий за N ³ операций), порядок которых очень важен, в матрице a мы фактически получим ответ на вопрос задачи. Распечатать его можно так:

for i:=1 to nn do

for j:=1 to nn do

if a[i,j] xor c[i,j] then writeln(i,’ ’,j);

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

4. Пути минимальной длины во взвешенном графе

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

Наиболее просто найти кратчайший путь между каждой из пар вершин можно с помощью алгоритма Флойда [5 – 7], основанного на той же идее, что и алгоритм Уоршолла. Пусть в элементе матрицы A [i , j ] хранится длина кратчайший пути из вершины i в вершину j , который проходит через некоторые вершины с номерами, не превосходящими k – 1. Если же длины пути из вершины i в вершину k и пути из вершины k в вершину j то таковы, что их сумма меньше, чем значение данного элемента матрицы, то его следует переопределить. То есть в реализации алгоритма Уоршолла следует заменить операцию and на “+”, а or — на нахождение минимума из двух величин. Для реализации алгоритма массив a первоначально следует заполнить элементами матрицы смежности, обозначая отсутствие ребра между двумя вершинами “бесконечностью” — числом, заведомо превосходящим длину любого пути в рассматриваемом графе, но меньшим, чем максимальное значение используемого типа данных, чтобы было возможно выполнять с ним арифметические операции. В этом случае можно избежать дополнительных проверок.

Если же нам требуется найти сам кратчайший путь, а не его длину, то при каждом улучшении пути между двумя вершинами мы в соответствующем элементе вспомогательного массива (в программе — w) будем запоминать номер той вершины, через которую кратчайший путь проходит, а затем с помощью элегантной рекурсивной процедуры будем его печатать. Идея рекурсии заключается в том, что если мы знаем, что кратчайший путь от вершины i до вершины j проходит через вершину k , то мы можем обратиться к той же самой процедуре с частями пути от i до k и от k до j . Рекурсивный спуск заканчивается, когда на кратчайшем пути между двумя вершинами не окажется промежуточных вершин.

Приведем фрагмент программы, реализующий алгоритм Флойда и печатающий кратчайшие пути между всеми парами вершин графа.

procedure way(i,j:integer);

{печатает путь между вершинами i и j}

begin

if w[i,j]=0 then write(' ',j)

{печатаем только вершину j,

чтобы избежать повторов}

else

begin

way(i,w[i,j]); way(w[i,j],j)

end

end;

begin

…{заполняем матрицу смежности}

for k:=1 to nn do

for i:=1 to nn do

for j:=1 to nn do