Разработка алгоритмического и программного обеспечения для решения графовых задач (стр. 3 из 5)
2. B содержит расстояния – текущие кратчайшие рас- стояния от до соответствующей вершины;
3. третий массив с содержит номера вершин – k-й элемент С[k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний A[i,k] задает длины дуге A[i,k]; если такой дуги нет, то A[i,k] присваивается большое число Б, равное "машинной бесконечности".
Описание реализации:
1. Инициализация. В цикле от 1 до N заполнить нулями массив S; заполнить числом i массив C; перенести i-ю строку матрицы A в массив B, S[i]:=1; C[i]:=0 (i – номер стартовой вершины).
2. Общий шаг. Найти минимум среди неотмеченных (т. е. тех k, для которых S[k]=0); пусть минимум достигается на индексе j, т. е. B[j]<=B[k]
Затем выполняются следующие операции:
S[j]:=1;
если B[k] > B[j]+A[j,k], то (B[k]:=B[j]+A[j,k]; C[k]:=j)
(Условие означает, что путь Vi ... Vk длиннее, чем путь Vi...Vj Vk).
(Если все S[k] отмечены, то длина пути от Vi до Vk равна B[k]. Теперь надо перечислить вершины, входящие в кратчайший путь).
3. Выдача ответа. (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)
z:=C[k];
Выдать z;
z:=C[z]. Если z = О, то конец,
иначе перейти к 3.2.
Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т. е. алгоритм Дейкстры имеет квадратичную сложность: O(n2).
Отыскание кратчайшего пути имеет естественную интерпретацию в терминах матриц. Пусть A – матрица цен одной аваиакомпании, а B – матрица цен другой. Считается, что диагональные элементы матриц равны 0. Можно доказать, что эта матрица вычисляется по обычной формуле для произведения матриц, только вместо суммы надо брать минимум, а вместо умножения – сумму.
Обычное умножение матриц тоже может оказаться полезным, только матрицы должны быть другие. Пусть есть не все рейсы (как в следующем разделе), а только некоторые, a[i,j] равно 1, если рейс есть, и 0, если рейса нет. Возведем матрицу a (обычным образом) в степень k и посмотрим на ее i-j-ый элемент. Он равен числу различных способов попасть из i в j за k рейсов.
Случай, когда есть не все рейсы, можно свести к исходному, введя фиктивные рейсы с бесконечно большой (или достаточно большой) стоимостью.
4. Нахождение остовного дерева минимального веса
Постановка задачи:
Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной.
Всякую прикладную постановку задачи нелишне уточнить. Мы негласно подразумеваем, что города сравнительно со страной малы; поэтому мы пренебрежем величиной городов и будем изображать город (точнее: телефонную станцию, размещенную в городе) точкой. Введя подходящую систему декартовых координат, мы запишем положение i-го города, парой координат (
). Условие, что страна плоская, означает, что 
— расстояние от i-го города, до j-го, задается формулой 
В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-м, а j-й с k-м, то i-й связан с k-м. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. Уточненную задачу можно теперь переформулировать в терминах теории графов.
В терминах теории графов задача Прима-Краскала выглядит следующим образом:
Дан полный граф с n вершинами, длины ребер определяются по формуле (1), где
- координаты вершин. Найти остовное дерево минимальной длины.В таком виде задача была поставлена и решена Примом (1961). Краскал, одновременно и независимо, поставил и решил задачу не для плоского случая, где расстояния определяются по формуле (1), а для произвольных положительных
. При этом для некоторых пар индексов 
, что означает отсутствие ребра, т.е. рассматривается любой граф, а не только полный.Итак, вышеприведенный вариант есть, строго говоря, задача Прима, а задача Краскала звучит так: Дан граф с n вершинами; длины ребер заданы матрицей D[i,j]. Найти остовное дерево минимальной длины.
Обе перечисленные задачи решаются одним алгоритмом, причем алгоритмом самой примитивной разновидности.
Представим себе, что зимовщику оставлен некоторый запас продуктов, и его задачей является составление вкусного меню на всю зиму. Если зимовщик начнет с того, что сперва будет есть самую вкусную еду (например, шоколад), потом — вторую по вкусности (например, мясо), то он рискует оставить на последний месяц только соль и маргарин. Подобным образом, если оптимальный (для определенности, минимальный) объект строится как-то по шагам, то нельзя на первом шаге выбирать что-то самое малое, на втором шаге — оставшееся самое малое и т. д. За такую политику обычно приходится жестоко расплачиваться на последних шагах. Алгоритм, который мы привели, называется жадным.
В задаче Прима-Краскала жадный алгоритм дает точное оптимальное решение.
Как известно (это легко доказать, скажем, по индукции), дерево с nвершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы не возникали циклы).
Алгоритм Прима-Краскала
(краткое описание)
1. В цикле n-1 раз делай: выбрать самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными.
Выбранные таким образом ребра образуют искомое остовное дерево.
Чтобы новое ребро не образовывало цикла со старыми, до построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра (x,y), где x и у имеют разные цвета, вершина у и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет x. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет.
Итак, более подробный алгоритм выглядит так.
Алгоритм Прима-Краскала
1. Инициализируем граф - вводим матрицу весов графа D[i,j]
2. "Раскрашиваем" вершины графа в разные цвета
3. До тех пор, пока число ребер остова меньше числа вершин графа, выполняем:
1) Находим ребро минимальной длины, не включенное до этого в остов графа и не образующее цикла с остовом
2) Включаем найденное ребро минимальной длины в остов
3) Меняем цвет всех вершин, входящих в остов, на один цвет
Докажем, что описанный алгоритм получает в точности минимальное решение.
Для доказательства нам понадобится очень простое утверждение:
Если к дереву добавить ребро, то в дереве появится цикл, содержащий это ребро.
Действительно, пусть добавлено ребро (u, v) – «добавлено» означает, что ребро – новое, что раньше его в дереве не было. Поскольку дерево является связным графом, то существует цепь С(u, ..., v) из нескольких ребер, соединяющая вершины uи v. Добавление ребра (u, v) замыкает цепь, превращая ее в цикл.
Теорема.Алгоритм Прима-Краскала получает минимальное остовное дерево.
Доказательство.Результатом работы алгоритма является набор из n-1 ребер. Они не образуют цикла, ибо на каждом из n-1 шагов соединялись вершины разного цвета, т. е. ранее не связанные. Этот граф связный, потому что после проведения 1-го ребра осталось n-1 разных цветов, ..., после проведения (n-1)-го ребра остался один цвет, т. е. одна компонента связности. Итак, полученный набор ребер образует связный граф без циклов, содержащий n-1 ребер, т. е. n вершин. Следовательно, граф есть остовное дерево.
Осталось доказать, что оно имеет минимальную длину. Пусть {
} ребра остовного дерева в том порядке, как их выбирал алгоритм, т. е. 
. Предположим для простоты доказательства, что все ребра сети имеют разную длину, т.е. 
(2)Если полученное дерево не минимально, то существует другое дерево, задаваемое набором из n-1 ребер {
}, такое что сумма длин 
меньше суммы длин 
. С точностью до обозначений 
(3)Может быть,
, 
и т.д., но так как деревья разные, то в последовательностях (2) и (3) найдется место, где ребра отличаются. Пусть самое левое такое место – k, так что 
(kможет равняться единице, это не испортит доказательства). Поскольку выбиралось по алгоритму самым малым из необразующих цикла с .ребрами 
, то 
. Теперь добавим к дереву (3) ребро 
в нем появится цикл, содержащий ребро и, может быть, какие-то (или все) ребра из , но они сами не образуют цикла, поэтому в цикле будет обязательно ребро d из набора 
, причем 
Выбросим из полученного графа с одним циклом ребро d; мы снова получим дерево, но оно будет на 
короче минимального, что невозможно. Полученное противоречие доказывает теорему для сети со всеми разными ребрами.