АЛГОРИТМЫ ПОСТРОЕНИЯ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ И КРАТЧАЙШЕГО ОСТОВА ГРАФА

Цель работы: изучение алгоритмов на графах

Теоретические сведения

1. Построение кратчайшего пути между двумя вершинами.

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

Для определения кратчайших расстояний от фиксированной начальной вершины до всех вершин ориентированного графа воспользуемся алгоритмом Форда-Беллмана. Обозначим через C – матрицу весов дуг графа (вес несуществующей дуги в задачах поиска минимума расстояний считаем равным +¥ ), D – массив кратчайших расстояний от начальной вершины s до всех вершин графа (полагаем ).

{ for ( ) ; ;

for ( )

}

Для произвольного ориентированного графа, не содержащего циклы отрицательного веса, такие кратчайшие расстояния можно вычислить максимум за итерации. На k-ой итерации алгоритма для каждой из вершин графа, кроме начальной, выполняется пересчёт кратчайших расстояний до неё от начальной вершины. Для этого определяется минимум из текущего значения расстояния до вершины и длин путей через другие вершины графа.

Количество итераций вычисления массива D можно уменьшить, сравнивая массивы в конце текущей и предыдущей

итерации (аналогично, алгоритмам сортировки). Если значения массива D не изменились на данной итерации, то вычисления заканчиваются.

Алгоритм восстановления кратчайшего пути от начальной вершины s до конечной вершины t использует механизм стека. В нём применяются следующие обозначения:

1) СТЕК – поместить вершину v в стек;

2) СТЕК – извлечь вершину v из стека.

{ СТЕК: =Æ; СТЕК ; ;

while ( )

{ for ( )

if ( )СТЕК ;

;

}

Конечная вершина пути заносится в стек, и пока верхушка стека v не совпадёт с начальной вершиной s, будет определяться предыдущая вершина пути u, т.е. вершина, на которой достигается минимум.

2. Построение кратчайшего остова.

Напомним, что остовом называется остовный подграф, который является деревом. Остов, суммарный вес которого минимален, называется кратчайшим остовом.

Для построения кратчайшего остова воспользуемся алгоритмом Краскала. Обозначим через – строящийся кратчайший остов, разбиение множества вершин остова на классы эквивалентности по отношению связанности вершин – .

Предварительно рёбра упорядочиваются в порядке возрастания весов. Обозначим , . Вначале , разбиение содержит n компонент связности, каждая компонента связности содержит одну вершину, т.е. . Программно разбиение можно реализовать как вектор, состоящий из множеств.

{ T: = Æ; ;

for ( i = ) ;

for ( j = )

{ ; ;

if ( ( ) Ù ( ) Ù ( ) )

{ ; ;

;

}

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

Пример выполнения работы.

1. Рассмотрим ориентированный граф, заданный следующим входным файлом. Построим графическое представление графа, определяемого этим файлом.

1 2 1

1 5 3

2 3 3

2 4 3

2 5 8

3 4 1

3 5 -5

4 3 2

5 4 4

Матрица весов дуг данного графа имеет вид

Пусть . Вычислим минимальные расстояния от вершины s до всех вершин графа. Выполним один шаг алгоритма Форда-Беллмана подробно, затем результаты работы алгоритма представим в виде таблицы.

Номер шага k	D

		¥	¥
				-1
				-1
				-1

Восстановим кратчайший путь от s до вершины .

, , так как

. В результате СТЕК имеет вид

Следовательно, кратчайший путь между вершинами 1 и 4, длина которого равна 3: 1 ® 2 ® 3 ® 5 ® 4.

2. Рассмотрим неориентированный граф, заданный следующим входным файлом. Построим графическое представление графа, определяемого этим файлом.

1 2 3

1 3 1

1 4 7

2 3 3

2 6 6

3 4 4

3 6 5

4 5 7

5 6 2

5 7 10

6 7 8

Перед построением остова , разбиение содержит 7 компонент, каждая компонента связности содержит одну вершину, т.е. .

Упорядочим рёбра в порядке возрастания весов. Результат работы алгоритма Краскала оформим в виде таблицы. Обозначим через:

– ребро графа;

– вес ребра ;

– вес остова.

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


(1, 3)
(5, 6)
(1, 2)
(2, 3)
(3, 4)
(3, 6)
(2, 6)
(1, 4)
(4, 5)
(6, 7)
(5, 7)

Таким образом кратчайший остов графа суммарного веса имеет вид

Контрольные вопросы

1. Каким образом находится кратчайший путь между двумя фиксированными вершинами?

2. Объясните основную идею алгоритма Форда-Беллмана.

3. Как определяется кратчайшее расстояние до вершины на каждой итерации?

4. Как восстанавливается кратчайший путь по найденным кратчайшим расстояниям?

5. Что называется кратчайшим остовом?

6. Объясните основную идею алгоритма Краскала.

Задание для лабораторной работы.

1. Для ориентированного графа варианта, заданного файлом вида «таблица рёбер», определить вручную кратчайшие расстояния от вершины 1 до всех остальных вершин графа, используя алгоритм Форда-Беллмана. Восстановить кратчайший путь от вершины 1 до вершины графа, имеющей максимальный номер. Отчёт должен содержать:

a) текст входного файла, графическое представление графа и матрицу весов дуг;

b) выполнение одного шага алгоритма Форда-Беллмана вручную подробно и таблицу пошагового вычисления массива кратчайших расстояний D;

c) стек восстановления кратчайшего пути между вершинами 1 и с объяснением и восстановленный кратчайший путь.

2. Для неориентированного графа варианта, заданного файлом вида «таблица рёбер» построить кратчайший остов графа, используя алгоритм Краскала. Отчёт должен содержать:

a) текст входного файла и графическое представление графа;

b) построение вручную кратчайшего остова;

c) графическое представление кратчайшего остова.

Лабораторная работа №8

⇐ Предыдущая 1 234 Следующая ⇒