Алгоритм Дейкстра
Code
// Алгоритм Дейкстра
#include <stdio.h>
#include <conio.h>
#include <locale.h>
#include <iostream>
#define numtop 6 //Число вершин в графе
int v;
using namespace std;
int main ()
{
setlocale(LC_ALL, "russian");
int top1 = 0, // Для ввода вершин
top2 = 0, // Для ввода вершин
toptop = 0;
cout<<"количество вершин графа >: 6\n";
int **Matrix = new int*[numtop];
for (int i = 0 ; i < numtop ; i++)
Matrix[i] = new int[numtop];
for (int i=0; i<numtop; i++)
{
for (int j=0; j<numtop; j++)
Matrix[i][j]=0;
}
cout<<"Введите список ребер: \n";
cout<<"Для прекращения ввода на очередной запрос введите несуществующие вершины \n";
while (1)
{
cout<<"ИЗ ";
cin>>top1;
cout<<"В ";
cin>>top2;
cout<<"РАССТОЯНИЕ ";
cin>>toptop;
if (top1<numtop && top2<numtop)
{
Matrix[top1][top2]=toptop;
Matrix[top2][top1]=toptop;
}
else
break;
}
// Вывод на экран матрицы смежности
cout<<"\nМатрица смежности:\n";
for (int i=0; i<numtop; i++)
{
for (int j=0; j<numtop; j++)
printf ("%2d", Matrix[i][j]);
cout<<"\n";
}
int infinity=1000; // Бесконечность
int p=numtop;
int s;
int g;
cout<<"Введите начальную вершину: ";
cin>>s;
cout<<"Введите конечную вершину: ";
cin>>g;
int x[numtop]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[numtop]; //t[i] - длина кратчайшего пути от вершины s в i
int h[numtop]; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути
// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u<p;u++)
{
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной
while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u<p;u++)
{
if(Matrix[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+Matrix[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+Matrix[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
}
// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u<p;u++) // Перебираем все вершины.
{
if(x[u]==0 && t[u]<w) // Если для вершины не найден кратчайший
// путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}
if(v==-1)
{
cout<<"Нет пути из вершины "<<s<<" в вершину "<<g<<"."<<endl;
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
cout<<"Кратчайший путь из вершины "<<s<<" в вершину "<<g<<":";
u=g;
while(u!=s)
{
cout<<" "<<u;
u=h[u];
}
cout<<" "<<s<<". Длина пути - "<<t[g];
break;
}
x[v]=1;
}
getch();
getch ();
return 0;
}