Нахождение минимального пути в графе

1 2 3 4 5 6 7

Курсовая работа

по курсу «Дискретная математика»

Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов

Вариант №…

Содержание курсовой работы

Пояснительная записка к курсовой работе должна содержать следующие разделы:

· постановка задачи;

· теоретическая часть;

· описание алгоритма решения поставленной задачи;

· ручной просчет (на небольшом примере показать работу алгоритма);

· описание программы;

· тесты;

· список использованной литературы;

· листинг программы.

ЗАДАНИЯ К КУРСОВОЙ РАБОТЕ

Раздел 1. Некоторые базисные алгоритмы обработки графов

Нахождение минимального пути в графе

Путь в орграфе D из вершины v в вершину w, где v ¹ w, называется минимальным, если он имеет минимальную длину среди всех путей орграфа D из v в w.

Назовем орграф D = (V, X) нагруженным, если на множестве дуг X определена некоторая функция l: X ® R, которую часто называют весовой функцией. Значение l (x) будем называть длиной дуги x. Предположим, что l (x) ³ 0. Длиной пути П в нагруженном орграфе будем называть величину l (П), равную сумме длин дуг, входящих в П, при этом каждая дуга учитывается столько раз, сколько она входит в данный путь.

Нагруженный орграф можно задать с помощью матрицы весов С (D) = { c_ij } _nxn с элементами

l (v_i,v_j), если (v_i,v_j) Î X,

c_ij =

¥, если (v_i,v_j) Ï X.

ЗАДАНИЕ 1. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Дейкстры.

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

Пусть s – начальная вершина, t – конечная вершина. На каждой итерации любая вершина v имеет метку l ^*(v), которая может быть постоянной или временной. Постоянная метка l ^*(v) – это длина кратчайшего пути от s к v, временная метка l (v) – это вес кратчайшего пути из s в v, проходящий через вершины с постоянными метками. Если на каком-то шаге метка становится постоянной, то она остается такой до конца работы алгоритма.

Вторая метка Q(v) – это вершина, из которой вершина v получила свою метку.

А л г о р и т м Д е й к с т р ы

Данные: матрица весов С (D) орграфа D, начальная вершина s.

Результат: расстояния от вершины s до всех вершин орграфа D: D [ v ] = d(s,v), v Î V, а также последовательность вершин, определяющая кратчайший путь из s в v.

1. Положим l ^*(s) = 0 и будем считать эту метку постоянной. Для всех v Î V, v ¹ s, положим l ^*(v) = ¥ и будем считать эти метки временными. Положим p = s.

2. Для всех vÎГp с временными метками выполним: если l^*(v)>l^*(p)+l(p,v), то l^*(v)=l^*(p)+l(p,v) и Q (v) =р. Иначе l^*(v) и Q (v) не менять, т.е. l^*(v) = min (l^*(t), l^*(p)+c_pv). (Идея состоит в следующем: пусть p – вершина, получившая постоянную метку l^*(p) на

предыдущей итерации. Просматриваем все вершины vÎГp, имеющие временные метки. Метка l^*(v) вершины vÎГp заменяется на l^*(p)+l(p,v), если оказывается, что ее метка l^*(v)>l^*(p)+l(p,v). В этом случае говорим, что вершина v получила свою метку из вершины p, поэтому положим Q (v) = p. С помощью этих дополнительных меток будем потом восстанавливать сам путь. Если l^*(v) £ l^*(p)+c_pv, то метки остаются прежними.

3. Пусть V * - множество вершин с временными метками. Найдем вершину v * такую, что l^*(v*) = min l^*(v), v Î V *. Считать метку l^*(v*) постоянной для вершины v *.

4. Положим p = v *. Если p = t, то перейдем к п.5 (l^*(t) – длина минимального пути). Иначе перейдем к п.2.

5. Найдем минимальный путь из s в t, используя метки Q (v): П = s… Q (t)t.

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

ЗАДАНИЕ 2. Найти минимальные пути от фиксированной вершины до произвольной вершины графа, используя алгоритм Форда-Беллмана.

Большинство известных алгоритмов нахождения расстояния между двумя фиксированными вершинами s и t опираются на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг C вычисляются некоторые верхние ограничения D [ v ] на расстояния от s до всех вершин vÎV. Каждый раз, когда мы устанавливаем, что D [ u ] + c_uv < D [ v ], оценку D [ v ] улучшаем: D [ v ] = D [ u ] + c_uv.

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Можно показать, что значение каждой из переменных D [ v ] равно тогда d(s,v) - расстоянию от s до v. Заметим, что для того, чтобы определить расстояние от s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Описанная общая схема является неполной, т.к. она не определяет очередности, в которой выбираются вершины u и v. Эта очередность оказывает сильное влияние на эффективность алгоритма. Опишем алгоритм Форда-Беллмана для нахождения расстояния от фиксированной точки s до всех остальных вершин графа.

Рассмотрим орграф D = (V, X), где V ={ v ₁,…, v_n }.

А л г о р и т м Форда – Беллмана

Данные: матрица весов С (D) орграфа D, начальная вершина s.

Результат: расстояния от вершины s до всех вершин орграфа D: D [ v ] = d(s,v), v Î V.

1. Всем вершинам vÎV орграфа присвоим метку D [ v ] = c_sv. Вершине s присвоим метку D [ s ] = 0.

2. Положим k =1.

3. Выберем произвольную вершину v Î V \ { s }.

4. Выберем произвольную вершину u Î V.

5. Положим D [ v ] = min (D [ v ], D [ u ] + c_uv).

6. Если вершина u пробежала еще не все множество вершин V, то выбрать среди оставшихся произвольную вершину и вернуться к шагу 5.

7. Если вершина v пробежала еще не все множество вершин V \ { s }, то выбрать среди оставшихся произвольную вершину и перейти к шагу 4.

8. Если k < n -2, то положить k=k +1 и вернуться к шагу 3, иначе алгоритм заканчивает свою работу, полученные значения D [ v ] будут равны расстояниям d(s,v) в орграфе D.

Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины s до вершины v.

Отметим, что закончить вычисления можно, когда выполнение цикла по k не вызывает изменения ни одной из переменных D [ v ].

Пример. Определим минимальные пути из вершины v ₁ до всех остальных вершин в нагруженном орграфе D, изображенном на рис. 1.

v₄

v₁5 2 2 v₂

5 2

2 1 v₃

12 v₅ 2

v₆

Рис.1.

Ниже в таблице приведены матрица весов, а также все вычисления по шагам.

	v₁	v₂	v₃	v₄	v₅	v₆	D⁽⁰⁾	D⁽¹⁾	D⁽²⁾	D⁽³⁾	D⁽⁴⁾
v₁	¥	¥
v₂	¥	¥	¥	¥	¥		¥
v₃	¥		¥	¥	¥	¥
v₄	¥		¥	¥	¥	¥
v₅	¥	¥			¥	¥
v₆	¥	¥	¥	¥	¥	¥

На первом шаге всем вершинам vÎV орграфа присвоим метку D [ v ] = c_sv, где s = v ₁. Выберем следующую вершину v ₂. Ей присвоим метку D [ v ₂] = min (D [ v ₂], D [ u ] + c_uv), где u Î V, т.е. D [ v ₂] = min (D [ v ₂], D [ v ₃]+ c ₃₂, D [ v ₄]+ c ₄₂, D [ v ₅]+ c ₅₂, D [ v ₆]+ c ₆₂ ) = ( ¥, 5+2, 5+2, 2+¥, 12+¥) = 7. Зафиксируем, что эта метка может быть получена из вершин 3 или 4.

Аналогично корректируются метки всех оставшихся вершин, а именно,

D [ v ₃] = min (D [ v ₃], D [ v ₂]+ c ₂₃, D [ v ₄]+ c ₄₃, D [ v ₅]+ c ₅₃, D [ v ₆]+ c ₆₃ ) = ( 5, 7+¥, 5+¥, 2+1, 12+¥) = 3,

D [ v ₄] = min (D [ v ₄], D [ v ₂]+ c ₂₄, D [ v ₃]+ c ₃₄, D [ v ₅]+ c ₅₄, D [ v ₆]+ c ₆₄ ) = ( 5, 7+¥, 3+¥, 2+2, 12+¥) = 4,

D [ v ₅] = min (D [ v ₅], D [ v ₂]+ c ₂₅, D [ v ₃]+ c ₃₅, D [ v ₄]+ c ₄₅, D [ v ₆]+ c ₆₅ ) = ( 2, 7+¥, 3+¥, 4+¥, 12+¥) = 2,

D [ v ₆] = min (D [ v ₆], D [ v ₂]+ c ₂₆, D [ v ₃]+ c ₃₆, D [ v ₄]+ c ₄₆, D [ v ₅]+ c ₅₆ ) = ( 12, 7+2, 3+¥, 4+¥, 2+¥) = 9.

Т.к. метки вершин изменились, то продолжаем процесс дальше. Результаты третьей и четвертой итераций совпали, значит итерационный процесс можно закончить, кроме того k = n -2 = 4.

Величины, стоящие в последнем столбце, и дают длины минимальных путей из вершины v ₁ до всех остальных вершин. Например, длина минимального пути из v ₁в v ₂ равна 5, сам путь имеет вид: v ₁ v ₅ v ₃ v ₂.

ЗАДАНИЕ 3. Найти минимальные пути между всеми парами вершин, используя алгоритм Флойда.

Очевидно, что задачу определения расстояния между всеми парами вершин можно решить, используя n раз (поочередно для каждой вершины) один из описанных ранее алгоритмов. Однако оказывается, что n -кратное использование этих алгоритмов не является наилучшим методом. Рассмотрим более эффективный алгоритм для решения поставленной задачи – алгоритм Флойда.

Идея этого алгоритма следующая. Рассмотрим орграф D = (V, X), где V ={ v ₁,…, v_n }. Обозначим через d_ij⁽^m⁾ длину кратчайшего из путей из v_i в v_j с промежуточными вершинами из множества { v₁,…,v_m }.

Тогда имеем следующие уравнения:

d_ij⁽⁰⁾ = c_ij,

d_ij⁽^m⁺¹⁾ = min (d_ij⁽^m⁾, d_im⁽^m⁾ + d_mj⁽^m⁾).

Обоснование второго уравнения достаточно простое. Рассмотрим кратчайший путь из v_i в v_j с промежуточными вершинами из множества { v₁,…, v_m,v_m₊₁ }. Если этот путь не содержит v_m₊₁, то d_ij⁽^m⁺¹⁾= d_ij⁽^m⁾. Если же он содержит v_m₊₁, то, деля путь на отрезки от v_i до v_m₊₁ и от v_m₊₁ до v_j, получаем равенство d_ij⁽^m⁺¹⁾ = d_im⁽^m⁾ + d_mj⁽^m⁾. Приведенные уравнения дают возможность вычислить расстояния d(v_i,v_j) = d_ij⁽ⁿ⁾, где 1 £ i, j £ n.

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

Данные: матрица весов С(D) орграфа D.

Результат: расстояния между всеми парами вершин D [ i,j ] = d(v_i,v_j).

1. Для всех i = 1,…, n, j = 1,…, n положим D [ i,j ] = c_ij.

2. Для всех i = 1,…, n положим D [ i,i ] = 0.

3. Положим m = 1.

4. Положим i = 1.

5. Положим j = 1.

6. D [ i,j ] = min (D [ i,j ], D [ i,m ] + D [ m,j ]).

7. Если j < n, то положим j = j + 1 и переходим к шагу 6.

8. Если i < n, то положим i = i + 1 и переходим к шагу 5.

9. Если m < n, то положим m = m + 1 и перейдем к шагу 4, иначе алгоритм заканчивает работу. Полученные значения D [ i,j ] дают расстояния между вершинами v_i и v_j.

Замечание. Дополнить описанный алгоритм шагами, позволяющими находить сам путь от вершины v_i до вершины v_j.

Пример. Определим длины минимальных путей между любыми парами вершин орграфа, изображенного на рис.1. Все вычисления будем проводить с помощью матриц D.

m = 1 m = 2

v₁

v₂

v₃

v₄

v₅

v₆

v₁

v₂

v₃

v₄

v₅

v₆

v₁

v₂

v₃

v₄

v₅

v₆

Положим m = 1. Если i = 1 или j = 1, то элементы матрицы остаются без изменения, т.к. D [ i,j ] = min (D [ i,j ], D [ i,m ] + D [ m,j ]). Поэтому рассмотрим случай, когда i = 2, а j = 3. Тогда D [ 2,3 ] = min (D [ 2,3 ], D [ 2,1 ] + D [ 1,3 ]) = min (¥,¥+5) = ¥. Далее, j = 4, т.е. D [ 2,4 ] = min(D [ 2,4 ], D [ 2,1 ] + D [ 1,4 ]) = min (¥,¥+5) = ¥. Продолжаем процесс до тех пор, пока i £ 6 и j £ 6. Положим m = 2и продолжим рассуждения дальше.