8.5. Минимальная путевая матрица Если по путевой матрице мы можем определить, имеется ли путь между вершинами v, и vj, то минимальная путевая матрица содержит длины кратчайших путей (количество дуг) между вершинами у,-и vj, i,j = 1,2,...,и.

Алгоритм вычисления минимальной путевой матрицы получается модификацией алгоритма Уоршалла. В матрице смежности все нулевые элементы меняются на бесконечность (число > n), а выражение для вычисления элемента минимальной путевой матрицы принимает вид:
Pij= min {pij, (ри, +pkj)).

Алгоритм, как и при вычислении путевой матрицы, выполняется за n проходов. После к-ro прохода рц содержит минимальную длину пути (в дугах) между вершинами / и j, который не проходит через вершины с номерами, большими к. После к-то прохода за минимальную длину пути между вершинами / и у принимается более короткая из двух:

1) длина пути, которая была вычислена до этого, т.е. пути, проходящего только через вершины с номерами, меньшими к;
• 2) длина пути, проходящего через вершину к, причем пути (i-k) и (k-j) также проходят только через вершины с номерами, меньшими к.

Иногда необходимо знать не только минимальный путь между вершинами i и j, но и вершины, через которые пролегает этот путь (маршрут). Для этого дополнительно вводится матрица М„*„, в которой элемент /гг(/ содержит номер вершины к, полу-ченный при нахождении наименьшего значения /?/,- при к-и прохождении. Если pij = 0, то это значит, что вершины i и у смежны.
printf("\n"); } /* Вычисление минимальной путевой матрицы */
pm(A,P,M,n);
printf("\n Минимальная путевая матрица:\п");
for (i=0;i<n;i++)
{for (j=O;j<n;j++)
printf(" %d ",P[i][j]==1OOOO ? 0 : P[i][j]);
printf("\n"); }
/* вывод маршрута между всеми парами вершин 7 for (i=1; i≤n; i++)
for 0=1; j≤n; j^
) MinPath(M,P,n,ij);
return 0;

8.6. Кратчайшие пути Ha практике часто требуется найти наилучший маршрут от одной вершины графа до другой. Что означает «наилучший»? Наилучший маршрут могут определять многие факторы:

• расстояние в км;
• время прохождения маршрута;
• вероятность передачи сообщения по сетям связи;
• пункты, которые необходимо посетить, и т.д.

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

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

• двумя заданными вершинами;
• данной вершиной и всеми остальными вершинами; каждой парой вершин и т.д.

8.6.1. Алгоритм Дейкстры Одним из наилучших алгоритмов отыскания кратчайшего пути между двумя вершинами является алгоритм Дейкстры [8], который по существу совпадает с алгоритмом Прима [8] отыскания остовного дерева минимального веса. Рассмотрим алгоритм Дейкстры отыскания кратчайшего пути от заданной начальной вершины v до конечной вершины w. Граф G=(V,E) имеет т вершин, вершины пронумерованы 1,2,...,т. Граф представлен взвешенной матрицей смежности А^т*т, где ау _ длина дуги, соединяющей вершины i и j. Если дуга отсутствует, то принимается ац - бесконечность (число, большее длины наибольшей дуги графа).

В результате вычислений получаем перечень дуг, лежащих на кратчайшем пути и представленных тройками чисел: начальная вершина, конечная вершина и длина пути от заданной вершины v до конечной вершины дуги. Фактически этот перечень можно рассматривать как дерево с корнем v, узлы дерева содержат номера вершин графа, длины означают расстояния от корня (заданной вершины v) до этих вершин. Обратный обход дерева от заданной конечной вершины w до начальной v дает перечень вершин, лежащих на искомом кратчайшем пути.

Алгоритм Дейкстры состоит в следующем.

1. Выбираем начальную вершину v, от которой до другой заданной вершины w отыскивается кратчайший путь. Остальные (т - 1) вершины включаем в перечень невыбранных вершин. Определяем расстояния от заданной начальной вершины v до всех остальных вершин.
2. По наименьшему расстоянию выбираем новую вершину, исключив ее из перечня невыбранных. Число невыбранных вершин уменьшаем на 1. Дугу перехода, определившую наименьшее расстояние, включаем в перечень дуг кратчайшего пути.
3. Определяем расстояния от новой выбранной вершины до всех невыбранных с учетом пройденных от начальной точки v расстояний. Если расстояние до некоторой вершины меньше ранее определенного, то заменяем его новым значением. Отбираем наименьшее расстояние и переходим к новой вершине, исключив ее из перечня невыбранных. Число невыбранных вершин уменьшаем на 1. Дугу перехода включаем в перечень дуг кратчайшего пути и т.д., пока не достигнем заданной конечной вершины w при поиске кратчайшего пути между двумя вершинами v и к- или не выберем все n вершин графа при поиске кратчайших путей от вершины v до всех остальных.

Алгоритм Дейкстры относится к «жадным» алгоритмам. «Жадность» заключается в том, что на каждом шаге к списку выбранных вершин добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин. В то же время этот алгоритм использует метод динамического программирования, так как на каждом шаге выбирается оптимальное значение, которое затем не пересчитывается.

Процесс выполнения алгоритма можно проследить на примере графа, представленного на рис. 8.8, в качестве начальной и конечной вершин выбраны вершины 1 и 8 соответственно.

Рис. 8.8. Поиск кратчайших путей в графе

8.6.2. Алгоритм Флойда Иногда требуется решать общую задачу нахождения кратчайших путей, т.е. нахождения для каждой пары вершин (u,v) пути от вершины v к вершине iv. длина (расстояние) которого минимальна среди всех возможных путей от г к и\ Эту задачу можно решить, последовательно применяя алюритм Дсйкстры нахождения кратчайших путей для каждой вершины. Тогда временная сложность будет равна О(п) при использовании матрицы смежности и O(n*e*log(n)) при использовании списков смежности.

Существует прямой способ решения этой задачи, использующий алгоритм Флойда. Граф G=(V,E) с п вершинами пред¬ставляется взвешенной матрицей смежности S_n*n. В результате решения задачи формируется матрица А„*„, в которой элемент fly будет содержать значение кратчайшего пути от вершины i до вершины j.

Сначала исходная матрица S копируется в матрицу А, причем если дуга (ij) отсутст-вует, то ац - °°, а диагональные элементы ПЦ = 0. Алгоритм выполняется за п проходов. После к-то прохода fly-содержит значение наименьшей длины путей из вершины / к j, которые не проходят через вершины с номером, большим к, т.е. между вершинами i и j могут быть вершины только с номерами, меньшими или равными к. При к-м проходе элемент ац вычисляется как A_k[i,j] = mm(A_k.\[i, j], A_kA[i, к] + А_кл[к,Д) (см. рис. 8.7).

Алгоритм Флойда реализуется посредством трех вложенных циклов и имеет сложность О(п^г). Часто необходимо знать не только кратчайшее расстояние между вершинами v и w, но и вершины, через которые пролегает кратчайший путь. Для этого дополнительно используется матрица М„*„, в которой элемент тц содержит номер вершины к, полученный при нахождении наименьшего значения ац в к-м проходе. Если а_у- = 0, то вершины i uj смежны. Ниже приводится программа нахождения кратчайших рассто¬яний по алгоритму Флойда.

8.7. Остовные деревья графа

Остовным деревом для связного неориентированного графа G = (V,E) с п вершинами называется неориентированное дерево, содержащее все и вершин и (п - 1) ребер графа. Таким образом, остовное дерево связывает все вершины графа и из каждой вершины графа можно попасть в любую другую. В полном графе с п вершинами имеется п"' остовных деревьев. Для одного и того графа можно построить несколько остовных деревьев (рис. 8.9).

Рис. 8.9. Граф (а) и ею остовные деревья (б) и (в)

Пусть G = (V,E) — связный неориентированный граф и Т = {V,F) — остовное дерево для него. Тогда из [2]:

а) для любых двух вершин v, и у,- путь между ними единствен;
б) если к остовному дереву Г добавить ребро из {E-F), т.е. из оставшихся, не включенных в дерево ребер графа, то возникнет ровно один цикл и Т перестанет быть деревом.

Под остовным деревом ориентированного графа понимают такое дерево, в котором одна из вершин графа связана со всеми остальными. Основными задачами нахождения остовных деревьев графа являются:

• нахождение остовного дерева;
• нахождение минимального и максимального остовного дерева.

8.8. Обходы графов. Поиск в глубину и поиск в ширину При решении многих задач, связанных с графами, необходим систематический обход вершин и дуг (ребер) графа. Широкое применение получили два метода обхода:

• поиск в глубину;
• поиск в ширину.

При поиске в глубину осуществляется регулярный обход графа по правилам.

1. Находясь в вершине v, нужно двигаться в любую другую н>, ранее не пройденную вершину (если таковая найдется), одновременно запоминая дугу z, по которой мы впервые попали в вершину w.
2. Если из вершины v мы не можем попасть в ранее не пройденную вершину или таковой вообще нет, то мы возвращаемся в вершину дуги z, из которой впервые попали в вершину v, и продолжим поиск в глубину из этой вершины.

При поиске в глубину в ориентированном графе мы можем попасть в вершину vr из вершины v только в том случае, если в орграфе есть дуга (i',u), то есть двигаемся вперед только в направлении ориентации дуг, а возвращаемся против ориентации. В неориентированном графе таких ограничений нет. В неориентированном графе обход можно начинать с любой вершины. Топология полученного остовного дерева зависит от начальной вершины.

Рассмотрим особенности поиска в глубину в орграфе. Те дуги, которые ведут к новым вершинам, называются дугами дерева, или древесными дугами. Они формируют для данного графа либо остовное дерево (дерево поиска в глубину), либо остовный лес (глбинное остовное дерево, глубинный остовный лес). Для того чтобы после завершения обхода в глубину все вершины оказались пройденными и образовалось остовное дерево, необходимо и достаточно, чтобы обход начинался во входе графа (вершине, имеющей только исходящие дуги) и этот вход был единственным. В противном случае при обходе в глубину образуется глубинный остовный лес. Если при поиске в глубину вершины графа нумеруются в порядке их посещения, то такая нумерация называется глубинной нумерацией графа или М-нумерацией вершин графа [14]. После завершения поиска в глубину все дуги орграфа разбиваются на 4 класса:

1) класс Т (Tree) древесных дуг, порождающих дерево поиска в глубину либо глубинный остовный лес. Для каждой дуги (х,у)е Т имеем М(х)< М(у), М[г\ — номер вершины i;
2) класс F (Forward) прямых дуг, к которому относятся дуги (х,у), такие, что М(х) < М(у) и вершина х соединена с у путем, состоящим из древесных дуг. Другими словами, прямые дуги идут эт предков к непосредственным потомкам, но не являются древесными дугами;
3) класс В (Back) обратных дуг, представляющих дуги (х,у), гакие, что М(х) < М(у) и вершина у соединена с х путем, состояцим из древесных дуг. По-другому обратные дуги идут от потомков к предкам;
4) класс С (Cross) поперечных дуг, представляющих собой дуги х,у), такие, что М{х) > М(у) и вершины х и у не соединены путем, «стоящим из древесных дуг, т.е. поперечные дуги соединяют вер- нины, не являющиеся ни потомками, ни предками друг друга.

Рис. 8.10. Обход дерева в глубину

Если начать обход в глубину этого же графа, начиная с другой вершины, то образуется глубинный остовный лес. Например, обход, начиная с вершины с, приведет к образованию леса с двумя остовными деревьями. Первое дерево включает ребра (с, /), (f, h), (h,j), if, i), (i, g). Второе дерево с началом обхода в вершине а состоит из ребер (a, b), (b, d), (d, e). Для упражнения определите прямые, обратные и поперечные дуги графа, полученные в результате такого обхода.

При поиске в глубину в связном неориентированном графе образуется одно единственное глубинное дерево. В нем различают только два класса ребер: древесные и обратные. Сложность алгоритма поиска в глубину равна О(е), где е — число дуг (ребер) графа.

Ниже приводится пример вычисления остовного дерева по алгоритму поиска в глубину. Исходный граф представлен списками смежности.

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

1. Вначале выбираем некоторую вершину v, остальные (т - 1) вершины графа отмечаются как невыбранные.
2. Определяются веса между выбранной вершиной v и остальными невыбранными вершинами.
3. Выбираем вершину с наименьшим весом до нее, фиксируем выбранные ребро и вес.
4. Выбранную вершину исключаем из перечня невыбранных, число выбранных вершин уменьшаем на 1.
5. Пункты 1 — 4 повторяем до тех пор, пока не будут выбраны все вершины, т.е. (т - 1) раз.

Процесс поиска остовного дерева наименьшего веса по алгоритму Прима можно проследить на примере графа, приведенного на рис. 8.12. Приведенная программа демонстрирует определение остовного дерева минимального веса для неориентированного графа по алгоритму Прима

8.9. Остовное дерево наименьшей стоимости (минимального веса) Пусть G - (V, Е) — связный взвешенный неориентированный граф, для которого задана матрица смежности, отображающая веса ребер в числа (вещественные или це-лые). Стоимость (вес) остовного дерева определяется как сумма стоимостей (весов) его ребер. Цель — найти для графа G остовное дерево наименьшей стоимости (минимального веса). Полный граф с п вершинами содержит п"'² остовных деревьев. Поиск каждого остовного дерева занимает О(е) времени. В полном дереве е=п*(п-\)12. Тогда решение задачи прямым поиском имело бы сложность О(п"-² п(п - \)12)=О(п^п).

Рис. 8.11. Граф и его остовные деревья: а — исходный граф; 6 -- поиск в глубину; в— поиск в ширину

Рис. 8.12. Поиск остовного дерева наименьшего веса по алгоритму Прима

8.9.2. Алгоритм Крускала Пусть имеется связный взвешенный граф G( V,E) с п вершинами. Построение остовного дерева минимального веса начинается с графа Т=( V,0), имеющего только п вершин без ребер. Каждая вершина, таким образом, оказывается связанной только с самой собой. Построение дерева сводится к формированию набора связных компонент, постепенным объединением которых и формируется остовное дерево.

Упорядочим ребра множества Е в порядке возрастания их веса (стоимости). Выберем ребро с наименьшим весом С\ и включим в граф Т. Теперь в графе Т (п - 1) компонент содержит только по одной вершине, одна компонента содержит две вершины и одно ребро. Выбираем следующее наименьшее ребро. Если оно связывает две вершины из разных компонент, то это ребро добавляется в граф Т. Если же ребро связывает две вершины из одной компоненты, то такое ребро отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, приведет к образованию цикла. Когда все вершины графа будут принадлежать одной компоненте, построение остовного дерева минимального веса Т с (и - 1) ребрами заканчивается. Процесс построения остовного дерева минимального веса можно проследить на примере графа, приведенного на рис. 8.13. Ниже приводится программа нахождения остовного дерева минимального веса по алгоритму Крускала.

Упорядоченная таблица весов ребер графа

Рис. 8.13. Поиск остовного дерева наименьшего веса по алгоритму Крускала

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

В толковом словаре одни слова определяются с помощью других. Топологическая сортировка слов в словаре требует, чтобы все слова, участвующие в определении данного слова, находились в словаре раньше определяемого слова. В учебных программах вузов одни предметы опираются на материал других. Топологическая сортировка означает чтение курсов в таком порядке, чтобы ни один курс не читался раньше того курса, на материале которого он основан. Сетевые методы планирования и управления предполагают, что любая работа может быть выполнена только после того, как будут выполнены опорные работы. Пусть имеется ориентированный граф G-{V,E) с произвольно занумерованными вершинами v,-, i = 1,2,...,и. Граф является упорядоченным, если в отношении каждой его дуги О,,^) справедливо неравенство v,

Рассмотрим граф, представленный на рис. 8.14, а). Из рисунка видно, что вершина 3 имеет ранг R=0, вершина 1 имеет ранг R=l, вершины 5 и 7 имеют ранг R=2. вершина 4 имеет ранг R=3, вершина 2 имеет ранг R=4 и вершина 6 имеет ранг R=5.

Рис. 8.14. Неупорядоченный (а) и упорядоченный (б) графы

Алгоритм упорядочения графа состоит из двух этапов. На первом этапе определяются ранги вершин, на втором этапе осуществляется перенумерация их в соответствии с рангами. Единственной вершине v,, не имеющей входов, присваивается номер 0, а затем нумерация выполняется в порядке возрастания ранга вершины, причем нумерация вершин одного ранга безразлична. Упорядоченный граф имеет вершины v,- с номерами 0,1,2,...,/! - 1. Рассмотренный выше граф после упорядочения будет иметь нумерацию вершин, как показано на рис. 8.14, б).

Таким образом, исходным номерам вершин 1, 2, 3, 4, 5, 6, 7 после упорядочения соответствуют новые номера 1, 5, 0, 4 ,2, 6, 3. Ниже приводится программа [6], использующая для упорядочения графа метод Форда.