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

1. Введение

2. Теоретическая часть а) Основные понятия теории графов б) Понятия смежности, инцидентности, степени

в) Маршруты и пути г) Матрицы смежности и инцедентности

3. Алгоритм поиска минимального пути из в в ориентированном орграфе (алгоритм фронта волны)

4. Листинг программы

5. Примеры выполнения программы

6. Использованная литература

Введение

Развитие теории графов в основном обязано большому числу всевозможных приложений. По-видимому, из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.

Графы нашли применение практически во всех отраслях научных знаний: физике, биологии, химии, математике, истории, лингвистике, социальных науках, технике и т. п. Наибольшей популярностью теоретико-графовые модели используются при исследовании коммуникационных сетей, систем информатики, химических и генетических структур, электрических цепей и других систем сетевой структуры.

Благодаря своему широкому применению, теория о нахождении кратчайших путей в последнее время интенсивно развивается.

Нахождение кратчайшего пути — жизненно необходимо и используется практически везде, начиная от нахождения оптимального маршрута между двумя объектами на местности (напр. кратчайший путь от дома до академии), также используется в системах автопилота, используется для нахождения оптимального маршрута при перевозках коммутации информационного пакета Internet и мн. др.

Кратчайший путь рассматривается при помощи графов.

Цель курсовой работы:

Разработать программу поиска оптимального пути в ненагруженном ориентированном графе на любом языке программирования.

Теоретическая часть:

а) Основные понятия теории графов Теория графов как теоретическая дисциплина может рассматриваться как раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами. Как прикладная дисциплина теория графов позволяет описывать и исследовать многие физические, технические, экономические, биологические, социальные и другие системы. Например, графом, изображенным на рис. 1, в котором точки? вершины графа? города, линии, соединяющие вершины? ребра? дороги, соединяющие города, описывается так называемая транспортная задача (задача нахождения кратчайшего пути из одного городапункта в другой).

Рис. 1.

Формальное определение графа таково. Пусть задано конечное множество V, состоящее из n элементов, называемых вершинами графа, и подмножество X декартова произведения VЧV, то есть, называемое множеством дуг, тогда ориентированным графом D называется совокупность (V, X). Неориентированным графом G называется совокупность множества V и множества ребер? неупорядоченных пар элементов, каждый из которых принадлежит множеству V.

Одинаковые пары — параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Рис. 2.

Например, кратность ребра {v1,v2} в графе, изображенном на рис. 2, равна двум, кратность ребра {v3,v4}? трем.

Псевдограф? граф, в котором есть петли и/или кратные ребра.

Мультиграф? псевдограф без петель.

Граф? мультиграф, в котором ни одна пара не встречается более одного раза.

Граф называется ориентированным, если пары (v, w) являются упорядоченными.

Ребра ориентированного графа называются дугами.

Итак, используемые далее обозначения:

V — множество вершин;

X — множество ребер или дуг;

v (или vi) — вершина или номер вершины;

G, G0 — неориентированный граф;

D, D0 — ориентированный;

{v, w}? ребра неориентированного графа;

{v, v} - обозначение петли;

(v, w)? дуги в ориентированном графе;

v, w — вершины, x, y, z — дуги и ребра;

n (G), n (D) количество вершин графа;

m (G) — количество ребер, m (D) — количество дуг.

Примеры

1) Ориентированный граф D=(V, X), V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

Рис. 3.

2) Неориентированный граф G=(V, X), V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Рис. 4.

б) Понятия смежности, инцидентности, степени Если x={v, w} - ребро, то v и w? концы ребер.

Если x=(v, w) — дуга ориентированного графа, то v? начало, w — конец дуги.

Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).

Вершины v, w называются смежными, если {v, w}ОX.

Степенью вершины v графа G называется число d (v) ребер графа G, инцидентных вершине v.

Вершина графа, имеющая степень 0 называется изолированной, а степень 1 — висячей.

Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).

Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).

в) Маршруты и пути Последовательность v1x1v2x2v3… xkvk+1, (где kі1, viОV, i=1,…, k+1, xiОX, j=1,…, k), в которой чередуются вершины и ребра (дуги) и для каждого j=1,…, k ребро (дуга) xj имеет вид {vj, vj+1} (для ориентированного графа (vj, vj+1)), называется маршрутом, соединяющим вершины v1 и vk+1 (путем из v1 в vk+1).

Длина маршрута (пути)? число ребер в маршруте (дуг в пути).

г) Матрицы смежности и инцидентности Пусть D=(V, X) ориентированный граф, V={v1,…, vn}, X={x1,…, xm}.

Матрица смежности ориентированного графа D? квадратная матрица

A (D)=[aij] порядка n, где Матрица инцидентности? матрица B (D)=[bij] порядка nґm, где

Матрицей смежности неориентированного графа G=(V, X) называется квадратная симметричная матрица A (G)=[aij] порядка n, где

.

Матрица инцидентности графа G называется матрица B (G)=[bij] порядка nґm, где Алгоритм поиска минимального пути из в в ориентированном орграфе (алгоритм фронта волны)

1) Помечаем вершину индексом 0, затем помечаем вершины О образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.

2) Если или k=n-1, и одновременно то вершина не достижима из. Работа алгоритма заканчивается.

В противном случае продолжаем:

3) Если, то переходим к шагу 4.

В противном случае мы нашли минимальный путь из в и его длина равна k. Последовательность вершин теория орграф матрица алгоритм есть этот минимальный путь. Работа завершается.

4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем. Присваиваем k:=k+1 и переходим к 2).

Замечания Множество называется фронтом волны kго уровня.

Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько минимальных путей из в .

Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу минимальных расстояний R (D)между его вершинами. Это квадратная матрица размерности, элементы главной диагонали которой равны нулю (, i=1,., n).

Сначала составляем матрицу смежности. Затем переносим единицы из матрицы смежности в матрицу минимальных расстояний (, если). Далее построчно заполняем матрицу следующим образом.

Рассматриваем первую строку, в которой есть единицы. Пусть это строка? i-тая и на пересечении с j-тым столбцом стоит единица (то есть). Это значит, что из вершины можно попасть в вершину за один шаг. Рассматриваем j-тую сроку (строку стоит вводить в рассмотрение, если она содержит хотя бы одну единицу). Пусть элемент. Тогда из вершины в вершину можно попасть за два шага. Таким образом, можно записать. Следует заметить, что если в рассматриваемых строках две или более единиц, то следует прорабатывать все возможные варианты попадания из одной вершины в другую, записывая в матрицу длину наикратчайшего из них.

Листинг программы:

#include

#include

using namespace std;

int main ()

{

int N=0,n=0,c=0,i=0,k=0;

cout<<" ———————————————————————" <

cout<<" |Poisk optimalnogo puti v nenagrujennom orgrafe|" <

cout<<" ———————————————————————" <

case1:

cout<<" Vvedite chislo vershin v orgrafe: «;

cin>>N;

if (N<=1)

{

cout<<" Kolichestvo vershin doljno bit'>1!!!" <

goto case1;

}

///МАТРИЦА смежности:

cout<<" Zapolnite matricu smejnosti (esli puti net, vvedite 0; esli put' est', vvedite 1):" ;

float** A = new float*[N];

for (i;i

A[i] = new float[N];

for (i=0;i

for (int k=0;k

{

cout<<" V" ;

printf («%d», i+1);

cout<<" ->V" ;

printf («%d», k+1);

cout<<'=';

scanf («%f», &A[i][k]);

if ((A[i][k]≠0)&&(A[i][k]≠1))

{

cout<<" Vvodite tol’ko 0 ili 1!" <

return 0;

}

if ((i==k)&(A[i][k]==1))

{

cout<<" Na glavnoi diagonali doljni bit' nuli!" <

return 0;

}

}

////Откуда и куда?(Начальная и конечная вершина в графе!!)

case2:

cout<<" Vvedite nachalnuiu vershinu: «;

cin>>n;

if (n>N)

{

cout<<" Net takoi vershini!" <

goto case2;

}

if (n==0)

{

cout<<" Net takoi vershini!" <

goto case2;

}

case3:

cout<<" Vvedite konechnuyu vershinu: «;

cin>>c;

if (c>N)

{

cout<<" Net takoi vershini!" <

goto case3;

}

if (c==0)

{

cout<<" Net takoi vershini!" <

goto case3;

}

///Массив, где записывается число шагов

int h=1;

float*B= new float[N];

for (i=0;i

{

B[i]=0;

}

//В массиве B[N-1] ищем вершины, которые достжимы из начала пути

//т.е за один шаг

for (k=0;k

{

if (A[n-1][k]==1)

B[k]=1;

}

//Элементы фронта волны

while (h<50)

{

for (i=0;i

{

for (k=0;k

{

if ((B[i]==h)&&(A[i][k]==1)&&(B[k]==0))

B[k]=h+1;

}

}

h++;

}

B[n-1]=0;

if (B[c-1]≠0)

{

///Вывод на экран таблицу

cout<<" nTablica stoimosti minimalnogo puti:" <

for (i=0;i

{

printf («%f «, B[i]);

}

//Поиск обратного пути

cout<<" nnOptimal’nii put'(v obratnom poryadke):n" <<" V" ;

printf («%d», c);

h=c-1;

int b=B[c-1];

while (b>0)

{

for (i=0;i

if ((A[i][h]==1)&&(B[i]==B[h]-1))

{

cout<<" V" ;

printf («%d», i+1);

h=i;

b—;

}

}

cout<<" n" ;

}

else

{

cout<<" nPuti net! n" ;

}

delete A, B;return 0;

}

Примеры выполнения программы:

1.

2.

3.

Использованная литература:

1. «Теория графов». Методические указания по подготовке к контрольным работам по дисциплине «Дискретная математика». Сост.: Н. И. Житникова, Г. И. Федорова, А. К. Галимов. — Уфа, 2005 -37 с.

2. Курс лекций по дискретной математике Житникова В.П.

3. «Самоучитель С++», Перевод с англ. -3 изд. — СПб.: БХВ-Петербург, 2005 — 688 с.

4. «Дискретная математика для программистов», Ф. А. Новиков.

5. «Введение в дискретную математику», Яблонский.

6. «Курс дискретной математики», Неферов, Осипова.

7. «Информатика» Л. З. Шауцукова.