6. Вычисление расстояния между узлами ориентированного графа

Напомним, что расстоянием между двумя узлами n1иn2называется длина кратчайшего пути между этими узлами. Очевидно, что представляет интерес не только значение расстояния между двумя узлами, но и перечень узлов, входящих в кратчайший путь. Для решения этой задачи необходимо переопределить типtNode, включив в него дополнительные поля:Dist– расстояние до данного узла от некоторого другого узла,PrevNode– указатель на узел, предшествующий текущему в кратчайшем пути. Начальное значение поляDistдля всех узлов равно нулю. Определяем расстояния от узлаn1до всех остальных узлов графа, для чего последовательно обходим граф от узлаn1по спискам смежностии в полеDistузла, являющегося концом очередной дуги, записываем значение, равное сумме уже вычисленного расстояния до начального узла дуги плюс 1. Изменять значение поляDistконечного узла дуги надо только в том случае, если оно меньше того значения, которое в этом поле хранится (расстояние – длина кратчайшего пути до узла). При каждом изменении значения поляDistнеобходимо переопределять значение поляPrevNode, записывая в него указатель на тот узел, длина пути от которого до текущего узла оказалась меньшей.

Дополнительно необходимо хранить сведения об уже пройденных узлах (можно использовать поле Visitedлогического типа), чтобы не посещать их повторно. Начальное значение этого поля для всех узлов равноFalse. В основе алгоритма вычисления кратчайшего пути между узламиn1иn2лежит рекурсивный обход графа в глубину.

Метод tOrGraph.SPathвозвращает строку с перечнем информационных полей узлов графа (типаtValue=Char), входящих в кратчайший путь между узламиNode1иNode2. Длина кратчайшего пути (расстояние) равна длине этой строки, уменьшенной на 1.

functiontOrGraph.SPath(Node1,Node2:pNode):String;

// Кратчайший путь между узлами Node1 и Node2

procedurePathFromNode(Node:pNode);

// Внутренняя рекурсивная процедура

// вычисления расстояния от узла Node до всех узлов графа

var

Arc:pArc;// дуга графа

NextNode:pNode;// узел графа, следующий за Node

begin

Node^.Visited:=True; // отметка о посещении узла Node

Arc:=Node^.ArcList;// указатель на список смежности узла Node

whileArc<>nildo begin// пока не исчерпан список смежности узла Node

NextNode:=Arc^.RearNode; // узел, смежный с узлом Node

if not NextNode^.Visited

then begin // если узел NextNode еще не посещался,

NextNode^.Dist:=Node^.Dist+1;// то расстояние до него равно 1,

PathFromNode(NextNode);// продолжаем обход от него

NextNode^.PrevNode:=Node;// предыдущий узел для NextNode - Node

end

else// если узел NextNode уже посещался и,

ifNode^.Dist+1<NextNode^.Dist// длина пути к нему через узел Node меньше

then begin

NextNode^.Dist:=Node^.Dist+1;// то изменяем длину пути на меньшую и

NextNode^.PrevNode:=Node;// запоминаем узел, через который пришли

end;

Arc:=Arc^.NextArc;// переход к следующей дуге списка смежности

end;

end; // procedure PathFromNode

var

Node:pNode; // текущий узел графа

S:string;// строка – перечень узлов кратчайшего пути

begin

Node:=fHead;

// установка начальных значений всех узлов графа

while Node<>nil do begin

Node^.Visited:=False; Node^.Dist:=0;

Node:=Node^.NextNode;

end;

// вычисление расстояний от узла Node1 до всех остальных

PathFromNode(Node1);

Node:=Node2;s:=NodeValue(Node2);// включение Node2 в начало строки

whileNode<>Node1do begin

// для всех узлов в кратч. пути от Node2 до Node1

Node:=Node^.PrevNode;// переход к узлу, предшествующему Node2

Insert(NodeValue(Node),S,1);// включение предш. узла в начало строки

end;

SPath:=S;

end; // function tOrGraph.SPath

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