Лабораторная работа 15. Решение задачи о нахождении кратчайших расстояний на графе между двумя вершинами алгоритмами Беллмана-Калабы, Флойда, Дейкстры

 

Пусть задан ориентированный граф G=< E, V, H>, в котором для каждой дуги vÎ V задана длина с(v). На множестве вершин E выделены две вершины t и s. Требуется среди всех путей

t=i(0), v(1), i(1), v(2), i(2),..., v(k), i(k)=s,

соединяющих вершины t и s, где

h1(v(j))=i(j-1), h2(v(j))=i(j), jÎ [1..k],

c длиной

l= S{с(v(j)) | jÎ [1..k]},

определить путь, длина которого минимальна.

Обозначим через W(i) длину кратчайшего пути от вершины i до вершины s. Согласно принципа оптимальности Беллмана

W(s)=0,

W(i) = min{c(v)+W(h2(v))| vÎ V ^-(i)}, iÎ E\{s}.

Значение W(t) будет длиной кратчайшего пути от вершины t до вершины s. Для кратчайшего пути

t=i^~(0), v^~(1), i^~(1), v^~(2), i^~(2),..., v^~(k), i^~(k)=s,

справедливо равенство

W(i^~(j-1)) =c(v^~(j))+W(i^~(j))=min {c(v)+W(h2(v)) | vÎ V ^-(i^~(j-1)) }, jÎ [1..k].

 

Пример.

На графе G, приведенном в примере к лабораторной работе " Транспортная задача в сетевой постановке" найдем кратчайшее расстояние и путь между вершинами t=1 и s=9, в качестве длин дуг возьмем значения C из того же примера, выпишем кратчайший путь и его длину.

N=1, W(9, 1)=0,

W(8, 1)=min(2+W(9, 0))=2,

W(7, 1)=min(1+W(8, 0), 3+W(9, 0))=3,

W(6, 1)=min(6+W(9, 0))=6,

W(5, 1)=min(3+W(7, 0), 7+W(9, 0), 1+W(6, 0))=7,

W(4, 1)=min(4+W(7, 0), 1+W(5, 0))=M,

W(3, 1)=min(1+W(4, 0), 2+W(5, 0), 2+W(6, 0))=M,

W(2, 1)=min(6+W(8, 0), 1+W(7, 0))=M,

W(1, 1)=min(1+W(2, 0), 2+W(4, 0), 1+W(3, 0))=M.

N шага
i
	W(i, 0)	V	W(i, 1)	V	W(i, 2)	V	W(i, 3)	V	W(i, 4)	V
1=t	M		M	2	M	2	5	2	5	2
2	M		M	8	4	7	4	7	4	7
3	M		M	4	8	4	8	4	8	4
4	M		M	7	7	7	7	7	7	7
5	M		7	9	6	7	6	7	6	7
6	M		6	9	6	9	6	9	6	9
7	M		3	9	3	8	3	8	3	8
8	M		2	9	2	9	2	9	2	9
9=s	0		0		0		0		0

 

Кратчайший путь: 1 ® 2®7®8®9

Длина кратчайшего пути составит:

l=1+1+1+2=5

Задание.

1. На графе G приведенном в лабораторной работе " Транспортная задача в сетевой постановке" найти кратчайшее расстояние и путь между вершинами t и s, в качестве длин дуг взять значения C из той же лабораторной работы. Результаты работы представить в виде следующей таблицы, а также выписать кратчайший путь и его длину.

Таблица 1.

N шага
i
	W(i, 0)	W(i, 1)	W(i, 2)	W(i, 3)	W(i, 4)	W(i, 5)
1=t
2
3
4
5
6
7
8
9=s

 

 

2. Решить предыдущую задачу алгоритмом Флойда. Результаты представить в виде:

 

Таблица 2.

 

i	Значения W(i)
t
s

а также выписать кратчайший путь и его длину.

В каждой строке предыдущей таблицы выписывается последовательность значений W, получаемых на первом этапе.

 

Алгоритм Дейкстры отыскания кратчайших расстояний на графе.

 

Алгоритм Дейкстры применяется для случая, когда c(v)> 0. В нем каждая вершина может быть:

непомеченной,

помеченной временной пометкой,

помеченной постоянной пометкой.

Вершина i непомечена, если до нее не найден ни одного пути из вершины t. Помечена временной пометкой, если из вершины t найден путь и величина W(i) есть верхняя оценка кратчайшего расстояния от t до i, и на последующих итерация может быть уточнена вплоть до кратчайшего расстояния от t до i. Помечена постоянной пометкой, если W(i) из верхней оценки стала кратчайшим расстоянием от t до i. Алгоритм первого этапа заканчивает работу, если W(s) стало равным кратчайшему расстоянию от t до s.