Материал: АиСД. Практикум (in dev)

Min

В этом столбце минимальная длина, равная 27, указывает следующую вершину G,

к которой следует перейти, и т.д. Таким образом, получаем траекторию пути:

( L, B, G, S, D ).

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

Пусть в матрице A[i,j] записаны длины ребер графа (элемент A[i,j] равен весу ребра, соединяющего вершины с номерами i и j, если же такого ребра нет, то в соответствующем элементе записано некоторое очень большое число). Построим новые матрицы C_k[i,j] (k=0,…,N). Элемент матрицы C_k[i,j] будет равен минимально возможной длине такого пути из i в j, что в качестве промежуточных вершин в этом пути используются вершины с номерами от 1 до k. То есть рассматриваются пути, которые могут проходить через вершины с номерами от 1 до k , но заведомо не проходят через вершины с номерами от k+1 до N. В матрицу записывается длина кратчайшего из таких путей. Если таких путей не существует, записывается то же большое число, которым обозначается отсутствие ребра.

Если вычислена матрица C_k–1[i,j], то элементы матрицы C_k[i,j] можно вычислить по следующей формуле: C_k[i,j]:=min (C_k–1[i,j], C_k–1[i,k]+C_k–1[k,j]). В самом деле, рассмотрим кратчайший путь из вершины i в вершину j, который в качестве промежуточных вершин использует только вершины с номерами от 1 до k. Тогда возможно два случая:

Этот путь не проходит через вершину с номером k. Тогда его промежуточные вершины — это вершины с номерами от 1 до k–1. Но тогда длина этого пути уже вычислена в элементе C_k–1[i,j].

Этот путь проходит через вершину с номером k. Но тогда его можно разбить на две части: сначала из вершины i доходим оптимальным образом до вершины k, используя в качестве промежуточных вершины с номерами от 1 до k–1 (длина такого оптимального пути вычислена в C_k–1[i,k]), а потом от вершины k идем в вершину j опять же оптимальным способом, и опять же используя в качестве промежуточных вершин только вершины с номерами от 1 до k (C_k–1[k,j]).

Выбирая из этих двух вариантов минимальный, получаем C_k[i,j].

Последовательно вычисляя матрицы C₀, C₁, C₂ и т.д. получим искомую матрицу C_N кратчайших расстояний между всеми парами вершин в графе.

Алгоритм Флойда можно свести к последовательности шагов

Присвоить c_ij=0 для всех i=1,2,...,n и c_ij=, если в графе отсутствует дуга (x_i x_j). Присвоение начальных значений.     Шаг 1. присвоить k=0;     Шаг 2. k=k+1.     Шаг 3. Для всех i<>k, таких, что c_ik<>, и для всех j<>k, таких, что c_ik<>, с_ij= [min[c_ij, (c_ik+ c_kj)]. (9) Проверка на окончание.     Шаг 4. Если k=n, то матрица [с_ij] дает длины всех кратчайших путей.     Остановка. Иначе перейти к шагу 2.

41. Алгоритм Йена

Пусть граф задан матрицей A[i,j] . Вершина s выбрана как начальная. Найдём длины k наименьших путей до каждой вершины от вершины s (рёбра в одном пути могут повторяться неоднократно), при условии, что эти пути существуют. Результат будет храниться в матрице B, размером N*k, где N-количество вершин. Элемент массива B[i,j] равен j-му по длине пути до вершины i.

Для каждой вершины в массиве C будем хранить количество уже найденных до неё наименьших путей. Изначально все элементы массива C равны нулю. Все элементы матрицы B делаем равными, какой-нибудь большой константе, заведомо большей всех возможных путей. Во время исполнения алгоритма в матрице B будем хранить лучшие k путей до каждой вершины, найденные во время исполнения, при этом первые C[i] путей для вершины i найдены уже окончательно (элементы матрицы B, B[i,1], B[i,2], …, B[i,k] для всех i, упорядочены в возрастающем порядке).

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

Алгоритм Йена можно свести к последовательности шагов

Присвоение начальных значений.     Шаг 1. Найти P¹. Присвоить k=2. Если существует только один кратчайший путь P¹, включить его в список L₀ и перейти к шагу 2.     Если таких путей несколько, но меньше, чем К, включить один из них в список L_c, а остальные в список L₁. Перейти к шагу 2.     Если существует К или более кратчайших путей P¹, то задача решена. Остановка.     Нахождение отклонений.     Шаг 2. Найти все отклонения P_i^k(k-1)-го кратчайшего пути P^k-1 для всех i=1, 2, …, q_k-1, выполняя для каждого i шаги с 3-го по 6-й.     Шаг 3. Проверить, совпадает ли подпуть, образованный первыми i вершинами любого из P^j путей (j=1, 2,…,k-1). Если да, то присвоить c(x_i^k-1, x_i+1^j)=; иначе ничего не изменять. (При выполнении алгоритма вершина х₁ обозначается s).     Шаг 4. Найти кратчайшие пути S_i^k от x_i^k-1 к t, исключая из рассмотрения вершины s, x_i^k-1, x₃^k-1,..., x_i^k-1. Если существует несколько кратчайших путей, то взять в качестве S_i^k один из них.     Шаг 5. Построить P_i^k, соединяя R_i^k(=s, x^-1, x^-1,…, x^-1) c S и поместить Р в список L₁.     Шаг 6. Заменить элементы матрицы весов, измененные на шаге их первоначальными значениями и возвратиться к шагу 3.     Выбор кратчайших отклонений.     Шаг 7. Найти кратчайший путь в списке L₁. Обозначить этот путь P^k и переместить его из L₁ в L₀.   Если k=K, то остановка. Список L₀-список К-кратчайших путей.  

Если k<K, то присвоить k=k+1, перейти к шагу 2. Если в L₁ имеется более чем один кратчайший путь (h-путей), то поместить в L₀ любой из них и продолжать как выше до тех пор, пока увеличенное на h число путей, уже находящихся в L₁, не совпадет с К или не превысит его. Тогда остановка.

42. Алгоритм Беллмана- Форда

Пусть в матрице A[i,j] записаны длины ребер графа . Найдём наикратчайшие расстояния от заданной вершины s до всех остальных вершин графа. Алгоритм Беллмана-Форда решает эту задачу при наличии рёбер отрицательного веса. Обозначим через МинСт(s,v,к) наименьшую стоимость проезда из s в v менее чем с k пересадками. МинСт(s,v,k+1)=min(МинСт(s,v,k),МинСт(s,i,k)+A[i][v](i=1..n))

Искомым ответом является МинСт(s,i,n) для всех i=1..n.

Чтобы найти не только длины наименьших путей до всех вершин, но и сами эти пути используем следующий приём. Параллельно с вычислением массива x будем вычислять матрицу D[i,j]_. Если между вершинами s и j существует путь, то в элементе массива D [j,0] будет хранится количество вершин в этом пути, а цепочка вершин, составленная из элементов с D[j,1] по D[j,D[j,0]], будет этим самым путём. Путь до вершины s содержит единственную вершину (D[s,0]=1, D[s,1]=s). Для вычисления матрицы D потребуется немного дополнить текст процедуры:

k:= 1; for i := 1 to n do begin x[i] := a[s][i]; end;

{инвариант: x[i] := МинСт(s,i,k)} Обозначим через МинСт(s,i,к) наименьшую

стоимость проезда из s в i менее чем с k пересадками. Тогда выполняется такое

соотношение: for i := 1 to n do begin D[i,0]:=2; D[i,1]:=s; D[i,2]:=i; End;

D[s,0]:=1;

while k <> n do begin for i := 1 to n do begin for j := 1 to n do begin if x[i] > x[j]+a[j][i] then begin x[i] := x[j]+a[j][i];

D[i]:=D[j];

D[i,0]:=D[j,0]+1;

D[i,D[i,0]]:=i; end; end {x[i] = МинСт(s,i,k+1)} end; k := k + 1; end;

43. Литература

1. Т. Кормен, Ч. Лейзерсон, Р. Ривест

Алгоритмы: построение и анализ. М.: МЦНМО, 2000.

2. Д.Кнут Искусство программирования , том 1. Основные алгоритмы. Уч . пос. М.:Изд.

Дом " Вильямс ", 2000.

3. Вирт Н. Алгоритмы и структуры данных.: Пер. С англ. - М.: Мир, 2001.

4. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си.

Учеб. пособие. М : Финансы и статистика, 2004.

5. А. Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы М: СПб: Киев:

Вильямс, 2001г.

44. Лабораторное задание.

Для выполнения лабораторной работы необходимо:

1) Найти кратчайший путь методом динамического программирования для трех графов . Зафиксировать параметры каждого графа(число вершин и ребер), значение пути и время решения задачи (ориентированные графы);

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

Системы работает в диалоговом режиме с использованием «меню». Вся необходимая поясняющая информация отображается во время работы системы на экране монитора.

3) Изучить алгоритмы работы с графовыми структурами

Данная программа предназначена для демонстрации работы алгоритмов и облегчения понимания терминов теории графов.

Программа позволяет вводить, редактировать, сохранять графы в файл, загружать из файла. Также реализованы алгоритмы построения Эйлерова цикла, нахождения кратчайшего пути, нахождение пути, содержащего наименьшее количество вершин, решение задачи о раскраске вершин, задачи Коммивояжера.

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

При включенной кнопке «Выравнивать по сетке» новые вершины будут автоматически выравниваться по координатной сетке.

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

4) Ознакомиться с алгоритмами Флойда, Йена, Беллмана- Форда