1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include <vcl.h>
#include <iostream.h>
#include <conio.h>
#pragma hdrstop
#pragma argsused
#define VERTEXES 9 //Число вершин в графе
int v;
int main(int argc, char* argv[])
{
clrscr();
int infinity=1000; // Бесконечность
int p= VERTEXES; // Количество вершин в графе
int a[VERTEXES][VERTEXES]={ 0,1,0,0,1,3, // Матрица смежности графа
1,0,5,0,0,1,
0,5,0,5,20,1,
0,0,5,0,3,2,
1,0,20,3,0,10,
3,1,1,2,10,0 };
// Будем искать путь из вершины s в вершину g
int s; // Номер исходной вершины
int g; // Номер конечной вершины
cout<<"Введите s: "; // Номер может изменяться от 0 до p-1
cin>>s;
cout<<"Введите g: ";
cin>>g;
int x[VERTEXES]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[VERTEXES]; //t[i] - длина кратчайшего пути от вершины s в i
int h[VERTEXES]; //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(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[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();
} |
(
