Машинное представление графов

Логически граф может быть представлен матрицей смежности или матрицей инцидентности. Матрицей смежности для графа содержащего n узлов называется квадратная матрица adj порядка n.Элемент adj(i,j) равен 1, если узел j смежен с узлом i, иначе 0. Если граф неориентирован, то adj(i,j)=adj(i,j).

A B C D

A 0 1 0 0

B 0 0 1 1

C 0 0 0 1

D 1 0 1 0

Рис. .

Матрицы смежности используются для построения матриц путей. Значение adjk(i,j) показывает существует ли путь длиной k между узлами i и j. При этом adj_i= adj _i-1* adj.

матрица adj₂ матрица adj₃ матрица adj₄

A B C D A B C D A B C D

A 0 0 1 1 A 1 0 1 1 A 1 1 1 1

B 1 0 1 1 B 1 1 1 1 B 1 1 1 1

C 1 0 1 0 C 0 1 0 1 C 1 0 1 1

D 0 1 0 1 D 1 0 1 1 D 1 1 1 1

Рис. . Матрицы путей

Каждой дуге (A,B) исходного графа G поставим в соответствие число k(A,B) (рис. 2). Если в графе G отсутствует некоторая дуга (A,B), положим k(A,B) равной бесконечности. Будем называть число k(A,B) длиной дуги (A,B), хотя k(A,B) можно также интерпретировать как соответствующие затраты и соответствующий весовой коэффициент. Определим длину пути как сумму длин отдельных дуг составляющих этот путь.

Рис. .

 

Для любых двух вершин s и t графа G могут существовать несколько путей, соединяющих вершину s с вершиной t. Рассмотрим алгоритм, который определяет такой путь, ведущий из вершины s в вершину t, который имеет минимально возможную длину. Этот путь называется кратчайшим путем между вершинами s и t.

Алгоритм, предложенный в 1959 г. Дейкстрой, позволяет находить в графе кратчайший путь при положительных длинах дуг. Главная идея заключается в последовательном определении ближайших к s вершин (т.е. определяется 1-я ближайшая к s вершина, затем – 2-я, 3-я и т.д. до тех пор, пока следующая ближайшая вершина не окажется вершиной t ).

Алгоритм Дейкстры

– Шаг 1. Перед началом выполнения алгоритма все вершины и дуги не окрашены. Каждой вершине в ходе выполнения алгоритма приписывается число d(x), равное длине кратчайшего пути из s в x, включающего только окрашенные вершины. Положить d(s)=0 и d(x) равное бесконечности для всех x, отличных от s. Окрасить вершину s и положить y =s ( y - последняя из окрашенных вершин).

– Шаг 2. Для каждой неокрашенной вершины x следующим образом пересчитать величину

d(x)=min{ d(x),d(y)+a(x,y) } (1)

Если d(x) равно бесконечности, для всех неокрашенных вершин x закончить процедуру алгоритма: в исходном графе отсутствуют пути из вершины s в неокрашенные вершины. В противном случае окрасить ту из вершин x, для которой величина d(x) является наименьшей. Кроме того, окрасить дугу, ведущую в выбранную на данном шаге вершину x ( для этой дуги достигался минимум в соответствии с выражением (1) ). Положить y=x.

– Шаг 3. Если y=t, закончить процедуру: кратчайший путь из вершины s в вершину t найден (это единственный путь из s в t, составленный из окрашенных дуг). В противном случае перейти к шагу 2.

Отметим, что каждый раз, когда окрашивается некоторая вершина (не считая вершины s), окрашивается и некоторая дуга, заходящая в данную вершину. Таким образом, на любом этапе алгоритма в каждую вершину заходит не более чем одна окрашенная дуга. Кроме того окрашенные дуги не могут образовывать в исходном графе цикл, т.к. в алгоритме не может окрашиваться дуга, концевые вершины которой уже окрашены. Следовательно, окрашенные дуги образуют в исходном графе ориентированное дерево с корнем в вершине s. Это дерево называется ориентированным деревом кратчайших путей.

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

Алгоритм Форда.

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

а.) На шаге 2 алгоритма пересчёт величин d(x) с помощью соотношения (1) производится для всех вершин, а не только для неокрашенных. Следовательно, числа d(x) могут уменьшаться как для окрашенных, так и для неокрашенных вершин.

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

в.) Процедура алгоритма заканчивается только тогда, когда все вершины окрашены и когда после выполнения шага 2 ни одно из чисел d(x) не меняется.