Поиск оптимального маршрута в нагруженном ориентированном графе

Размещено на http://www.allbest.ru/

Поиск оптимального маршрута в нагруженном ориентированном графе

Содержание

Цель работы

Теория

Алгоритм и блок-схема

Программа

Список литературы

Цель работы

Цель работы является определение минимального пути в нагруженном ориентированном графе с помощью алгоритма Форда-Беллмана.

Краткая теория

Графом называется двуосновная модель <V, E; i >, где i - бинарное отношение множеств V и E, такое, что каждый элемент e О E находится в отношении i либо ровно с одним, либо ровно с двумя элементами множества V.

При этом элементы множества V называются вершинами графа, элементы множества E называются рёбрами графа, а отношение i - отношением инцидентности. Вершины, инцидентные одному и тому же ребру, называются смежными.

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими те точки, соответствующим вершинам которых ребра инцидентны.

Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v₀,e₁,v₁,e₂, ..., v_n-1,e_n,v_n, где v_i О V, i О [0,n], e_i О E, (v_i-1,e_i), (v_i,e_i) О I, i О [1,n]. Вершины v₀, v_n называются связанными данным маршрутом (или просто связанными). Вершину v₀ называют началом, а v_n - концом маршрута. Если v₀ = v_n, то маршрут называют замкнутым. Число n называется длиной маршрута.

Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом.

Алгоритм и блок-схема

Беллмана.

Данные: Ориентированный граф <V, E> с n вершинами с выделенным источником s О V, матрица дуг A[u, v], u, v ОV (граф не содержит контуров отрицательной длины).

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

1 begin

2 for v О V do D [v] := A[s, v]; D [s]:= 0;

3 for k  := 1 to n - 2 do

4 for v О V \ {s} do

5 for u О V do D [v] := min(D[v], D[u] + A [u, v])

6 end граф алгоритм беллман

Размещено на http://www.allbest.ru/

Докажем правильность этого алгоритма. Для этого обозначим через d(m)(v) длину кратчайшего из путей из s в v, содержащих не более m дуг (d(m)(v) = г , если не существует ни одного такого пути). Тогда имеем

d^(m+1)(v) = min{d^(m)(u) + a[u, v]: u О V}, v О V. (1)

В самом деле, для каждого uО V очевидно имеем

d^(m+1)(v) ёd^(m)(u) + a[u, v],

причем равенство появляется, когда u является предпоследней вершиной произвольного кратчайшего пути из s в v. Покажем теперь, что если при входе в очередную итерацию цикла 3

d (s, v) ё D[v] ё d^(m)(v) для всех v О V, (2)

то по окончании этой итерации

d (s, v) ё D[v] ё d^(m+1)(v) для всех v О V. (3)

Действительно, предполагая выполнение условия (2) и анализируя действие оператора в строке 5, мы видим, что по окончании итерации цикла 3 имеем

d (s, v) ё D[v] ё min{d^(m)(u) + a[u, v]: u О V},

что, принимая во внимание равенство (1) дает условие (3).

Отметим, что при входе в цикл 3 имеем

D[v] = d 1 (v), v О V,

следовательно, после выполнения n - 2 итераций этого цикла будут выполняться неравенства ,

d (s, v) ё D[v] ёd^(n-1)(v), v О V.

Теперь достаточно показать, что d(n-1)(v) = d (s, v). Это справедливо, поскольку каждый путь более чем с n - 1 дугами содержит контур, устранение которого не увеличивает длины пути (ведь мы предполагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма.

Очевидно, что временная сложность алгоритма есть O(n3). Мы можем, конечно, закончить вычисления, когда выполнение цикла 4 не вызывает изменения ни одной из переменных ПРЕДШ[v], v О V. Это может наступить для k < n - 2, однако такая модификация алгоритма не изменяет существенным образом его сложности. Для редких графов (m << n2) удобнее представлять граф списками инцидентности ПРЕДШ[v], v О V. Заменяя строку 5 на

for u О ПРЕДШ[v] do D [v] :=min(D[v], D[u] + A [u, v]),

получаем алгоритм со сложностью O(nm).

Работа алгоритма Форда - Беллмана проиллюстрирована на следующем рисунке (V = {1, ..., 5}, веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).



k	D[1]	D[2]	D[3]	D[4]	D[5]
	0	1	г	г	3
1	0	1	4	4	-1
2	0	1	4	3	-1
3	0	1	4	3	-1

Алгоритм нахождения кратчайшего пути

Данные: Расстояния D[v] от фиксированной вершины s до всех остальных вершин v О V, фиксированная вершина t, матрица весов ребер, A[u, v], u, v ОV.

Результаты: СТЕК содержит последовательность вершин, определяющую кратчайший путь из s в t.

begin

CTEK := Ж ; CTEK Ь t; v:= t;

while v g s do

begin

u := вершина, для которой D[v] = D[u] + A[u, v];

CTEK Ь u;

v:= u

end

end.

Размещено на http://www.allbest.ru/

Пусть <V, E> -ориентированный граф, | V|  = n, | E|  = m. Если выбор вершины u происходит в результате просмотра всех вершин, то сложность нашего алгоритма - O(n²). Если мы просматриваем только список ПРЕДШ[v], содержащий все вершины u, такие что u (r) v, то в этом случае сложность будет O(m).

Отметим, что в случае положительных весов ребер задача о кратчайшем пути в неориентированном графе легко сводится к аналогичной задаче для некоторого ориентированного графа. С этой целью достаточно заменить каждое ребро {u, v}двумя дугами б u, vси бv, uс , каждая с таким же весом, что и {u, v}. Однако в случае неположительных весов это приводит к возникновению контуров с неположительной длиной.

Далее будем всегда предполагать, что G = < V, E>является ориентированным графом, |V|  = n, |E|  = m. В целях упрощения изложения и избежания вырожденных случаев при оценке сложности алгоритмов будем исключать ситуации, при которых "большинство" вершин изолированные.

Будем также предполагать, что веса дуг запоминаются в массиве A[u, v], u, vО V (A[u, v] содержит вес a (u, v)).

Программа

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

#include <iostream.h>

#include <stdio.h>

void main()

{

float matrix[10][10],tmatrix[10][10];

int size,j,i;

float u;

u=999;

cout<<"Enter size of matrix \t 1<size<10 \t";//ввод размера матрицы

cin>>size;

cout<<"\nEnter cells (if the lenght is universal you should enter 0(zero))";

cout<<"\n\n";

for(j=1;j<=size;j++) //цикл ввода ячеек матрицы

{for(i=1;i<=size;i++)

{

cout<<" matrix["<<j<<"]["<<i<<"] = ";

cin>>matrix[i][j];

if(matrix[i][j]==0)

{

matrix[i][j]=u;

}

}

}

int n,k,sp;

int getchar();

while(getchar()!='q')

{

cout<<"\n\nEnter source point:";//ввод источника

cin>>sp;

for(n=1;n<=size;n++)

{

tmatrix[n][1]=u; //присвоение строки источника в т.м.

tmatrix[n][2]=matrix[n][sp];

}

for(k=1;k<=size;k++)

{

tmatrix[sp][k]=0;

}

for(k=3;k<=size;k++) //алгоритм Форда-Беллмана

{

for(n=1;n<sp;n++)

{tmatrix[n][k]=matrix[n][1]+tmatrix[1][k-1];

for(i=1;i+1<=size;i++)

{

if (matrix[n][i+1]+tmatrix[i+1][k-1]<=matrix[n][1]+tmatrix[1][k-1])

{

tmatrix[n][k]=matrix[n][i+1]+tmatrix[i+1][k-1] ;

}

}

}

for(n=sp+1;n<=size;n++)

{tmatrix[n][k]=matrix[n][1]+tmatrix[1][k-1];

for(i=1;i+1<=size;i++)

{

if (matrix[n][i+1]+tmatrix[i+1][k-1]<=matrix[n][1]+tmatrix[1][k-1])

{

tmatrix[n][k]=matrix[n][i+1]+tmatrix[i+1][k-1] ;

}

}

}

}

cout<<"\n";

int p;

float lenght;

cout<<"Enter point: ";//запрос точки и выборка наименьшего пути

cin>>p;

cout<<"\n";

lenght=tmatrix[p][1];//вывод ответа

for(k=2;k<=size;k++)

{

if(lenght>=tmatrix[p][k])

lenght=tmatrix[p][k];

}

if(lenght>=999)

{cout<<"ANSWER:";

cout<<"Lenght=Universal\n";

}

else

{

cout<<"ANSWER:";

cout<<"Lenght="<<lenght;

cout<<"\n";

}

float tmp,tmi;//поиск маршрута

char escape;

int way[10];

int l,m,r;

r=p;

cout<<"\n\nWay:";

l=0;

while(p!=sp)

{

for(i=1;i<=size;i++)

{

tmp=tmatrix[p][1];

for(k=2;k<=size;k++)

{

if(tmp>=tmatrix[p][k])

{tmp=tmatrix[p][k];

}

}

tmi=tmatrix[i][1];

for(k=2;k<=size;k++)

{

if(tmi>=tmatrix[i][k])

{

tmi=tmatrix[i][k];

}

}

if(tmp==tmi+matrix[p][i])

{

l=l+1;

way[l]=i;

p=i;

}

}

}

for(m=l;m>=1;m--)

{

cout<<"->"<<way[m];

}

cout<<"->"<<r;

cout<<"\n\nPress 'q' and push ENTER to escape or another button and ENTER to continue:";

cin>>escape;

}

}

Примеры

Размещено на http://www.allbest.ru/



Размещено на http://www.allbest.ru/

Список литературы

1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988.

2. Кук Д., Бейз Г. Компьютерная математика. - М.: Наука, 1990.

3. Нефедов В.Н., Осипова В.А. Курс дискретной математики. - М.: Издательство МАИ, 1992.

4. Лекции по теории графов. / Емеличев В.А., Мельников О.И. и др. М.: Наука, 1990.

5. Оре О. Теория графов. - М.: Наука, 1980.

6. Ж.-Л. Лорьер. Системы искусственного интеллекта. - М.: Мир, 1991.

7. Гаврилов С.П. Сапоженко А.А. Сборник задач по дискретной математике. - М.: Наука, 1978.

Размещено на Allbest.ru