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

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<stdio.h>

#include<iostream>

using namespace std;

int main()

{

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

cout<<" ----------------------------------------------"<<endl;

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

cout<<" ----------------------------------------------"<<endl;

case1:

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

cin>>N;

if(N<=1)

{

cout<<"Kolichestvo vershin doljno bit>1!!!"<<endl;

goto case1;

}

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

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

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

for(i;i<N;i++)

A[i] = new float[N];

for(i=0;i<N;i++)

for(int k=0;k<N;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 tolko 0 ili 1!"<<endl;

return 0;

}

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

{

cout<<"Na glavnoi diagonali doljni bit nuli!"<<endl;

return 0;

}

}

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

case2:

cout<<"Vvedite nachalnuiu vershinu: ";

cin>>n;

if(n>N)

{

cout<<"Net takoi vershini!"<<endl;

goto case2;

}

if(n==0)

{

cout<<"Net takoi vershini!"<<endl;

goto case2;

}

case3:

cout<<"Vvedite konechnuyu vershinu: ";

cin>>c;

if(c>N)

{

cout<<"Net takoi vershini!"<<endl;

goto case3;

}

if(c==0)

{

cout<<"Net takoi vershini!"<<endl;

goto case3;

}

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

int h=1;

float*B= new float[N];

for(i=0;i<N;i++)

{

B[i]=0;

}

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

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

for(k=0;k<N;k++)

{

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

B[k]=1;

}

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

while(h<50)

{

for(i=0;i<N;i++)

{

for(k=0;k<N;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<<" Tablica stoimosti minimalnogo puti:"<<endl;

for(i=0;i<N;i++)

{

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

}

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

cout<<" Optimalnii put(v obratnom poryadke): "<<"V";

printf("%d",c);

h=c-1;

int b=B[c-1];

while(b>0)

{

for(i=0;i<N;i++)

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

{

cout<<"V";

printf("%d",i+1);

h=i;

b--;

}

}

cout<<" ";

}

else

{

cout<<" Puti net! ";

}

delete A,B;return 0;

}