 |
Кратчайшие пути между всеми парами вершин
|
|
|
|
Общая задача нахождения кратчайших путей заключается в нахождении для каждой упорядоченной пары вершин (v, u) такого пути от вершины v в вершину u, что его длина будет минимальна среди всех возможных путей от v к u. Эта задача может возникнуть, например, если имеется компьютерная сеть и известно время прохождения сетевого пакета между соседними компьютерами. Требуется узнать время прохождения пакета от каждого компьютера к каждому или максимальный временной интервал для прохождения пакета. Или, допустим, дан взвешенный орграф, который содержит время полета по маршрутам, связывающим определенные города, и необходимо построить таблицу, где приводилось бы минимальное время перелета из одного города в любой другой.
Подобные задачи можно решить последовательно применяя алгоритм Дейкстры для каждой вершины, объявляемой в качестве начальной. Но существует прямой способ решения, использующий алгоритм Флойда.
Алгоритм Флойда использует матрицу Distance размера n× n, где n – количество вершин в графе, в которой вычисляются длины кратчайших путей. Вначале каждый элемент матрицы Distance равен соответствующему элементу матрицы смежности, диагональные элементы равны 0. Если в графе дуга между вершинами u и v отсутствует, то Distance [ u, v ] =∞.
Над матрицей Distance выполняется n итераций. После k -й итерации Distance [ i, j ] содержит значение наименьшей длины путей из вершины i в вершину j, которые не проходят через вершины с номером, большим k. Другими словами, между концевыми вершинами пути i и j могут находиться только вершины, номера которых меньше или равны k.
На k -й итерации для вычисления матрицы Distance применяется следующая формула:
Distance [ i, j ] = min (Distance [ i, j ], Distance [ i, k ] +Distance [ k, j ]).
|
|
|
Одновременно с матрицей расстояний ведется построение матрицы предков parent, которая необходима для востановления последовательности вершин, составляющих кратчайший путь. В элемент parent [ i, j ] записывается номер последней промежуточной вершины на пути от i к j.
Код алгоритма приведен в листинге 8.
public class FloydAlgm
{ // Алгоритм Флойда поиска кратчайших расстояний
// между всеми парами вершин
int[,] Distance; // матрица кратчайших путей
int[,] parent; // матрица предков
public FloydAlgm(graph g)
{
int i, j, k; // индексы
// инициализация
Distance = new int[g.kol_vershn, g.kol_vershn];
parent = new int[g.kol_vershn, g.kol_vershn];
for (i = 0; i < g.kol_vershn; i++)
{
for (j = 0; j < g.kol_vershn; j++)
{
if (g.matr_smeznosti[i, j] == 0) // если дуги нет, то
{
Distance[i, j] = 10000; // длина пути = бесконечности
parent[i, j] = -1;
}
else {
Distance[i, j] = g.matr_smeznosti[i, j];
parent[i, j] = i;
}
}
Distance[i, i] = 0;
parent[i, i] = i;
}
// основной цикл
for (k = 0; k < g.kol_vershn; k++)
{
for (i = 0; i < g.kol_vershn; i++)
{
if (i == k) continue;
for (j = 0; j < g.kol_vershn; j++)
{
if ((j == i) || (k == j)) continue;
if (Distance[i, k] + Distance[k, j] < Distance[i, j])
{
Distance[i, j] = Distance[i, k] + Distance[k, j];
parent[i, j] = k;
}
}
}
}
}
//метод печати кратчайшего пути
public void PrintPаth(int v_begin, int v_end)
{
if (v_begin == v_end)
{
// Console.Write(" {0} ", v_begin);
}
else if (parent[v_begin, v_end] == -1)
{
Console.WriteLine(" не существует пути между”);
Console.Write(“ {0} и {1} ", v_begin, v_end);
return;
}
else PrintPаth(v_begin, parent[v_begin, v_end]);
Console.Write(" {0} ", v_end);
}
// метод, возвращающий расстояние
public int DistanceValue(int s, int t)
{
return Distance[s, t];
}
}
Листинг 8. Реализация алгоритма Флойда
Время исполнения алгоритма Флойда равно O (n3). Это ничуть не лучше, чем n вызовов алгоритма Дейкстры, но на практике он работает эффективнее, так как циклы этого алгоритма очень короткие. Алгоритм Флойда примечателен еще и тем, что быстрее работает при представлении графа с помощью матрицы смежности.
Во многих задачах интерес представляет только сам факт существования пути, длиной не меньше единицы, от вершины i до вершины j. В качестве примера можно привести граф шантажиста, в котором наличие дуги от i к j означает, что лицо i владеет компроматом на персону j и может принудить ее сделать что угодно. Для лоббирования выгоднее нанять то лицо, которое имеет компромат на наибольшее количество людей. Этому человеку будет соответствовать та вершина в графе, из которой достижимо наибольшее количество других вершин. На языке теории графов такая задача называется построением транзитивного замыкания.
|
|
|
Транзитивным замыканием графа G называется ориентированный граф такой, что дуга между вершинами i и j существует тогда и только тогда, когда в графе существует путь от вершины i к j. Алгоритм Флойда можно приспособить для нахождения транзитивного замыкания. Но полученный в результате алгоритм еще до Флойда разработал С. Варшалл, поэтому в литературе часто алгоритм Флойда называют алгоритмом Флойда-Варшалла.
Если вес каждой дуги положить равным единице и выполнить алгоритм Флойда, то по матрице расстояний легко строится транзитивное замыкание: если Distance [ i, j ] < ∞, то дуга от вершины i к вершине j существует. Также легко выяснить, из какой вершины достижимо наибольшее количество вершин, для задачи о шантажисте.
Упражнения.
1. Разработайте эффективный алгоритм для поиска самого дешевого пути в графе со взвешенными вершинами(стоимостью пути от вершины s к вершине t является сумма весов всех вершин, входящих в путь).
2. Диаметром графа называется максимальное кратчайшее расстояние между всеми парами вершин графа. Разработайте алгоритм, который определяет диаметр ориентированного графа.
3. В ориентированном взвешенном графе все вершины имеют положительный вес. Контуром называется ориентированный цикл. Разработайте алгоритм для поиска в орграфе контура с минимальным весом.
4. Разработайте алгоритм для поиска самого длинного пути из заданной вершины.
5. Дан взвешенный граф, у которого и вершины, и ребра имеют положительный вес. Если ребро отсутствует, то его вес равен бесконечности. Приведите алгоритм, который строит путь минимальной стоимости. Стоимость пути определяется как сумма весов ребер и вершин, через которые проходит путь.
6. Корнем ациклического орграфа называется вершина r такая, что существуют пути, исходящие из этой вершины и достигающие всех остальных вершин орграфа. Разработайте алгоритм, который определяет имеет ли данный ациклический орграф корень.
|
|
|
7. Пусть с каждым ребром орграфа связано число r (u, v) (0≤ r (u, v) ≤1). Будем интерпретировать r (u, v) как надежность – вероятность того, что сигнал успешно пройдет по каналу из u в v. Считая, что события прохождения сигнала по различным каналам независимы, предложите алгоритм для нахождения наиболее надежного пути между двумя данными вершинами.
8. Разработайте алгоритм для решения следующей задачи: на олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их всех между собой? (Незнакомые люди могут познакомиться только через общего знакомого).
Остов минимального веса
Рассмотрим следующую задачу: во взвешенном связном графе требуется найти остов минимального веса. Эта задача часто возникает при проектировании, например, линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить некоторой системой каналов связи так, чтобы любые два центра были связаны либо непосредственно соединяющим их каналом, либо через другие центры и каналы, и чтобы общая длина (или стоимость) каналов связи была минимальной. В этой ситуации заданные центры можно считать вершинами полного графа с весами ребер, равными длинам (стоимости) соединяющих эти центры каналов. Тогда искомая сеть будет кратчайшим остовным подграфом полного графа.
Очевидно, что этот кратчайший остовный подграф должен быть деревом.
Так как полный граф Kn содержит nn-2 различных остовных деревьев, то решение этой задачи перебором вариантов потребовало бы чрезвычайно больших вычислений даже при малых n. Существуют эффективные алгоритмы, решающие эту задачу, например алгоритм Дж. Краскала (1956 г.) и Р. Прима (1957 г.), применимые к произвольному связному графу.
Алгоритм Краскала
Общая формулировка задачи об остове минимального веса (о кратчайшем остове): в связном взвешенном графе G порядка n найти остов минимального веса. Алгоритм Краскала, решающий эту задачу, заключается в следующем.
|
|
|
1. Строим граф T 1 = On + e 1, присоединяя к пустому графу на множестве вершин V(G) ребро e 1 Î E(G) минимального веса.
2. Если граф Ti уже построен и i < n -1, то строим граф T i +1 = Ti + ei +1, где ei +1 – ребро графа G, имеющее минимальный вес среди ребер, не входящих в Ti и не составляющих циклов с ребрами из Ti.
Докажем, что алгоритм Краскала всегда приводит к остову минимального веса, а именно, что при i < n -1 граф Ti +1 можно построить, и граф Tn -1 является остовом минимального веса графа G.
Действительно, граф Ti имеет ровно i ребер и поэтому при i < n -1 является несвязным. А так как граф G связен, то в нем есть по меньшей мере одно ребро, не составляющее циклов с ребрами графа Ti. Таким образом, нужное ребро e i +1 существует и граф Ti +1 можно построить.
Теперь рассмотрим граф Tn -1. Поскольку Tn -1 является графом порядка n и у него n -1 ребро, то это дерево. Остается доказать, что вес дерева Tn- 1 минимален. Предположим, что это не так, и существует какой-то граф G, на котором алгоритм выдает неправильный ответ. Среди всех остовов графа G минимального веса выберем такой остов Tmin, который имeет с деревом Tn -1 максимальное количество общих ребер. Пусть ei ={ a,b } – ребро дерева Tn -1, не содержащееся в Tmin и имеющее минимальный номер среди ребер дерева Tn -1, не входящих в Tmin (напомним, что в процессе построения дерева Tn -1 его ребра получили номера 1, 2,..., n -1). При добавлении в дерево Tmin ребра ei получим цикл. В этом цикле есть ребро e, не входящее в дерево Tn -1. Заменив в дереве Tmin ребро e на ei, получим новый остов Tnew = Tmin – e + ei. Но Tmin - остов минимального веса, следовательно, вес дерева w (Tnew) ≥ w(Tmin), отсюда вес ребра w (ei) ≥ w (e).
С другой стороны, присоединяя ребро e к Ti -1 (при i =1 полагаем Ti -1 = On), цикла не будет, поскольку ребра e 1, e 2,..., ei -1, e входят в дерево Tmin, и потому, если бы вес w (ei) был больше, чем w (e), при построении дерева Ti было бы выбрано ребро e вместо ei. Поэтому w (ei) = w (e) и w (Tnew) = w(Tmin).
Итак, Tnew - остов минимального веса. Число ребер, общих для деревьев Tnew и Tn -1, больше, чем число ребер, общих для Tmin и Tn -1, что противоречит выбору дерева Tmin. Полученное противоречие доказывает корректность алгоритма.
Реализация алгоритма Краскала приведена в листинге 9. Исходный граф задается списком смежности. Для проверки наличия цикла при добавлении ребра используется массив пометок Mark. Изначально каждая вершина помечена своим номером. Ребро-кандидат можно включать в дерево, если его вершины имеют разные пометки, то есть принадлежат разным компонентам связности. При добавлении ребра в остов, инцидентные ему вершины помечаются меньшей из двух пометок. Также корректируются пометки вершин, находящихся в той же компоненте связности.
|
|
|
internal class rebro_grapha: IComparable
{
internal int v { get; set; } // номера вершин,
internal int u { get; set; } // образующих ребро
internal int weight { get; set; } // вес ребра
// реализация интерфейса для сравнения ребер по весу
public int CompareTo(object obj)
{
rebro_grapha rg = (rebro_grapha)obj;
if (this.weight > rg.weight) return 1;
else if (this.weight == rg.weight) return 0;
else return -1;
}
}
public class AlgmKraskala
{ // алгоритм Краскала построения минимального остова
List<rebro_grapha> sp_reber; //список ребер графа
int[] Mark; // массив пометок
Graph OstTree; // остов графа
// конструктор, инициализирующий структуры данных
public AlgmKraskala(Graph g)
{
// преобразование графа в массив ребер
sp_reber = new List<rebro_grapha>();
Mark = new int[g.kol_v_n];
for (int i = 0; i < g.kol_v_n; i++)
{
List<rebro> rlist = g.sp_reber[i];
foreach (rebro r in rlist)
{
rebro_grapha rg = new rebro_grapha { v = i, u = r.v_na,
weight = r.ves };
sp_reber.Add(rg);
}
Mark[i] = i;
}
sp_reber.Sort(); // сортировка списка ребер
OstTree = new Graph(g.kol_v_n); // создание пустого графа
}
void AddRebro(rebro_grapha rg)
{ // метод добавления ребра в остов
rebro e = new rebro{ v_na = rg.u, ves = rg.weight};
OstTree.sp_reber[rg.v].Add(e);
}
internal Graph OstovTree()
{// метод построения остовного дерева
rebro_grapha first = sp_reber[0]; // самое легкое ребро
sp_reber.RemoveAt(0);
AddRebro(first); // включение первого ребра в остов
Mark[first.v] = Math.Min(first.v, first.u);
Mark[first.u] = Mark[first.v];
// основной цикл
int kol_vo_reber_in_otree = 1; // кол-во ребер в остове
int old_mark;
while (kol_vo_reber_in_otree < (OstTree.kol_v_n-1))
{
rebro_grapha tek_r = sp_reber[0]; //очередное ребро
sp_reber.RemoveAt(0);
// если включение ребра не приводит к циклу
if (Mark[tek_r.v]!= Mark[tek_r.u])
{ // включаем его в дерево
AddRebro(tek_r);
kol_vo_reber_in_otree++;
// изменяем массив пометок
if (Mark[tek_r.v] > Mark[tek_r.u])
{
old_mark = Mark[tek_r.v];
Mark[tek_r.v] = Mark[tek_r.u];
}
else
{
old_mark = Mark[tek_r.u];
Mark[tek_r.u] = Mark[tek_r.v];
}
for (int i = 0; i < Mark.Length; i++)
if (Mark[i] == old_mark)
Mark[i] = Mark[tek_r.v];
}
}
return OstTree;
} }
Листинг 9. Реализация алгоритма Краскала
Трудоемкость алгоритма Краскала O (nm). Действительно, упорядочивание m ребер занимает время O (m log m), основной цикл выполняется не более m раз, внутри него в цикле обрабатывается массив пометок Mark длины n, что и дает оценку трудоемкости.
Алгоритм Прима
Алгоритм Прима отличается от алгоритма Краскала только тем, что на каждом шаге строится не просто ациклический граф, а дерево. Именно:
1. Выбираем ребро e 1 ={ a, b } минимального веса и строим дерево T 1, полагая V(T 1) = { a, b }, E (T 1) ={ e 1}.
2. Если дерево Ti порядка i +1 уже построено и i < n -1, то среди ребер, соединяющих вершины этого дерева с вершинами графа G, не входящими в Ti, выбираем ребро ei +1 минимального веса. Строим дерево Ti +1, присоединяя к Ti ребро ei +1 вместе с его не входящим в Ti концом.
Доказательство корректности этого алгоритма аналогично приведенному выше. Код алгоритма приведен в листинге 10. Исходный граф задается списками смежности. Для хранения вершин остовного дерева используется множество vershiniDereva, так как для этой структуры данных проверка на вхождение в множество элемента равна константе и не зависит от размера множества. Можно было бы также использовать для этой цели массив пометок.
public class AlgmPrima
{
HashSet<int> vershiniDereva; // множество вершин остова
List<rebro_grapha> sp_reber; //список ребер исходного графа
Graph OstTree; // остовное дерево
// метод добавления ребра в остовное дерево
void AddRebro(rebro_grapha rg)
{
rebro e = new rebro { v_na = rg.u, ves = rg.weight };
OstTree.sp_reber[rg.v].Add(e);
}
// конструктор, инициализирующий структуры данных
public AlgmPrima(Graph g)
{
vershiniDereva = new HashSet<int>();
sp_reber = new List<rebro_grapha>();
for (int i = 0; i < g.kol_v_n; i++)
{ //создание списка всех ребер графа
List<rebro> rlist = g.sp_reber[i];
foreach (rebro r in rlist)
{
rebro_grapha rg = new rebro_grapha { v = i, u = r.v_na,
weight = r.ves };
sp_reber.Add(rg);
}
}
sp_reber.Sort(); // упорядочивание списка ребер
OstTree = new Graph(g.kol_v_n);
}
// метод построения остовного дерева по алгоритму Прима
internal Graph ostovTree()
{
int n = OstTree.kol_v_n;
// самое легкое ребро включается в остовное дерево
rebro_grapha first = sp_reber[0];
sp_reber.RemoveAt(0);
AddRebro(first);
vershiniDereva.Add(first.v);
vershiniDereva.Add(first.u);
// основной цикл
while (vershiniDereva.Count < n)
{
bool find = false; // флаг = выбрано ребро для дерева
for (int i = 0; (i < sp_reber.Count) && (!find); i++)
{
rebro_grapha tek_rebro = sp_reber[i];
if ((vershiniDereva.Contains(tek_rebro.v) &&
!vershiniDereva.Contains(tek_rebro.u)) ||
(!vershiniDereva.Contains(tek_rebro.v) &&
vershiniDereva.Contains(tek_rebro.u)))
{
find = true;
AddRebro(tek_rebro);
sp_reber.RemoveAt(i);
vershiniDereva.Add(tek_rebro.v);
vershiniDereva.Add(tek_rebro.u);
}
}
}
return OstTree;
}
}
Листинг 10. Реализация алгоритма Прима
Трудоемкость алгоритма Прима O (nm). Действительно, основной цикл выполняется n раз, а внутри этого цикла просматривается список из m ребер.
На рисунке 15 посередине приведен исходный граф, а справа и слева – его минимальные остовные деревья, построенные по алгоритмам Краскала и Прима. Числа на ребрах остовных деревьев обозначают последовательность их добавления. Легко видно, что остовные деревья абсолютно одинаковы, но порядок добавления в них ребер различен.
Рис. 15. Граф G и его минимальные остовные деревья
|
|
|
