Поиск оптимального пути в ненагруженном орграфе (стр. 2 из 2)
Чтобы найти расстояния в ориентированном графе, необходимо составить матрицу http://hghltd.yandex.com/yandbtm?url=http%3A//www.fos.ru/matemat/9228.html&text=%CF%EE%E8%F1%EA+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE+%EF%F3%F2%E8+%E2+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC+%E3%F0%E0%F4%E5+%2C+%F0%E5%F4%E5%F0%E0%F2&reqtext=%28%CF%EE%E8%F1%EA%3A%3A783+%26+%EC%E8%ED%E8%EC%E0%EB%FC%ED%EE%E3%EE%3A%3A22975+%26%26/%28-3+3%29+%EF%F3%F2%E8%3A%3A5309+%26+%E2%3A%3A0+%26+%EE%F0%E8%E5%ED%F2%E8%F0%EE%E2%E0%ED%ED%EE%EC%3A%3A42191+%26+%E3%F0%E0%F4%E5%3A%3A31618+%26%26/%28-3+3%29+%F0%E5%F4%E5%F0%E0%F2%3A%3A6724%29//6&dsn=530&d=2003257 - YANDEX_34минимальных расстояний 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 tol'ko 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<<"\nTablica stoimosti minimalnogo puti:"<<endl;
for(i=0;i<N;i++)
{
printf("%f ",B[i]);
}
//Поискобратногопути
cout<<"\n\nOptimal'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<N;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. «Информатика» Л.З.Шауцукова.