Автор работы: Пользователь скрыл имя, 25 Марта 2012 в 23:09, курсовая работа
Целью данной курсовой работы является написание программы, реализующей алгоритм Форда-Беллмана. Алгоритм направлен на нахождение расстояния от источника до всех вершин и нахождение кратчайшего пути из S в T.
1. Введение 3
2. Постановка задачи 4
1. Представление кратчайших путей, релаксация……………………5
3. Алгоритм Форда-Беллмана 8
1. Перечень используемых величин и их назначение………………10
2. Входные и выходные данные, диапазон изменений……………..10
3. Блок-схема алгоритма...……………………………………………11
4. Заключение………………………………………………………………..13
5. Список используемой литературы………………………………………14
6. Приложение A. Инструкция к использованию программы..…………..15
7. Приложение B. Код программы………………………………………….17
if(S>=0 && S<MaxVer)
{
for (i=0;i<MaxVer;i++)
{
Ras[i] = Ves[S][i];
if(Ras[i]<B)
Fi[i]=S+1;
else Fi[i]=0;
}
Ras[S] = 0;
Fi[S]=S+1;
int *Rask=new int[MaxVer];//матрица расстояний пред.итерации
Rask[S]=0;
for (k=0;k<MaxVer-1;k++)
{
for (i=0;i<MaxVer;i++)
{
Rask[i]=Ras[i]; //хранение расстояний пред.итерации
if ( i!=S)
{
for (j=0;j<MaxVer;j++)
{
if (Ras[j]<B && Ras[i] > Ras[j]+Ves[j][i])
{
Ras[i] = Ras[j]+Ves[j][i];
Fi[i]=j+1;
}
}
}
}
rev=0;
for(e=0;e<MaxVer;e++)
{
if(Ras[e]!=Rask[e])
{
rev=1;
break;
}
}
if(k<MaxVer-2 && rev!=1)
if(k==MaxVer-2 && rev==1)
{
cout<<"\nОбнаружен отрицательный контур\n";
otkn=1;
break;
}
}
if(otkn==0)
{
cout <<"Матрица рассояний: \n";
for (i=0;i<MaxVer;i++)
{
if(Ras[i]>=B)
cout<<'&'<<" ";
else
cout << Ras[i] << " ";
}
cout << endl;
}
}
else
{
cout<<endl<<"Данной вершины в графе нет!"<<endl;
continue;
}
break;
}
if(otkn==0)
{
int *Put=new int[MaxVer];
mi=0;
while(mi<3)
{
mi++;
cout<<"Введите конец: ";
cin>>T;
S++;
int nedos=0;
if(T>0 && T<=MaxVer)
{
int p=0;
int z=T;
while(z!=S)
{
if(Fi[z-1]==0)
{
nedos=1;
break;
}
Put[p]=z;
z=Fi[z-1];
p++;
}
Put[p]=S;
if(nedos==0)
{
cout << "Кратчайший путь: ";
for(p;p>=0;p--)
cout<<Put[p]<<" ";
cout<<endl;
}
else
cout<<"Вершина "<<T<<" недоступна из "<<S<<endl;
}
else
{
cout<<endl<<"Данной вершины в графе нет! "<<endl;
continue;
}
break;
}
}
}