Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.
Инициализация
Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Первый шаг
Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.
Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7.
Аналогично находим длины пути для всех других соседей (вершины 3 и 6).
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.
Второй шаг
Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 < 17, поэтому метка не меняется.
Ещё один сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна 22 (7 + 15 = 22). Поскольку 22<10000, устанавливаем метку вершины 4 равной 22.
Все соседи вершины 2 просмотрены, помечаем её как посещенную.
Третий шаг
Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.
Четвертый шаг
Пятый шаг
Шестой шаг
Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5, поскольку таким путем мы набираем минимальный вес, равный 20.
Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4.
Для вершины 6 получим вес 20 — 9 = 11 (совпал).
Для вершины 4 получим вес 20 — 6 = 14 (не совпал).
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.
Реализация алгоритма Дейкстры
Для хранения весов графа используется квадратная матрица. В заголовках строк и столбцов находятся вершины графа. А веса дуг графа размещаются во внутренних ячейках таблицы. Граф не содержит петель, поэтому на главной диагонали матрицы содержатся нулевые значения.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
Реализация на C++
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
103
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6
int main()
{
int a[SIZE][SIZE]; // матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
// Инициализация матрицы связей
for (int i = 0; i<SIZE; i++)
{
a[i][i] = 0;
for (int j = i + 1; j<SIZE; j++) {
printf("Введите расстояние %d - %d: ", i + 1, j + 1);
scanf("%d", &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// Вывод матрицы связей
for (int i = 0; i<SIZE; i++)
{
for (int j = 0; j<SIZE; j++)
printf("%5d ", a[i][j]);
printf("\n");
}
//Инициализация вершин и расстояний
for (int i = 0; i<SIZE; i++)
{
d[i] = 10000;
v[i] = 1;
}
d[begin_index] = 0;
// Шаг алгоритма
do {
minindex = 10000;
min = 10000;
for (int i = 0; i<SIZE; i++)
{ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]<min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
{
for (int i = 0; i<SIZE; i++)
{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
// Вывод кратчайших расстояний до вершин
printf("\nКратчайшие расстояния до вершин: \n");
for (int i = 0; i<SIZE; i++)
printf("%5d ", d[i]);
// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 - 1
ver[0] = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i<SIZE; i++) // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
{
int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод кратчайшего пути\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;
}
Результат выполнения
Назад: Алгоритмизация
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
#include <vector>
#include <string>
using namespace std;
int main() {
setlocale(LC_ALL, "Ru");
int p,temp=0,minindex,min,index;
cin >> p;
vector < vector<int>>mats(p,vector<int>(p));
vector<int>posev(p);
vector<int>Dlina(p);
for (int i = 0; i < p; i++) {
posev[i] = 1;
Dlina[i] = 100;
for (int j = 0; j < p; j++) {
cin >> mats[i][j];
}
}
int start,konec;
cin >> start>>konec;
Dlina[start - 1] = 0;
do {
min = 100;
minindex = 100;
for (int i = 0; i < p; i++) {
if ((posev[i] == 1) and (Dlina[i] < min)) {
min = Dlina[i];
minindex = i;
}
}
if (minindex != 100) {
for (int i = 0; i < p; i++) {
if (mats[minindex][i] > 0) {
temp = min + mats[minindex][i];
if (temp < Dlina[i]) {
Dlina[i] = temp;
}
}
}
posev[minindex] = 0;
}
} while (minindex < 100);
cout << Dlina[konec - 1]<<endl;
vector<int>ver(p);
int end = konec - 1;
ver[0] = konec;
int predv=1;
int wes = Dlina[end];
while (end != start-1) {
for (int i = 0; i < p; i++) {
if (mats[i][end]!=0) {
int temp = wes - mats[i][end];
if (wes== Dlina[i]) {
wes = temp;
end = i;
ver[predv]=i+1;
predv++;
}
}
}
}
for (int i = predv-1; i >=start-1; i--) {
cout << ver[i] << "->";
}
}
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
bool Board::FindPtch(const int _start, const int _end)
{
// Сюда добавляются клетки которые еще не проверенные
queue<int> _qu;
//здесь хранятся проверенные клетки(ключ), откуда мы пришли(значение)
std::map<int, int> _explored;
//добавляем первую клетку(начало)
_qu.push(_start);
int _prev_step = 0/* родитель*/, _step = 0 /* следующая клетка */;
while (!_qu.empty()) // пока есть не проверенные клетки
{
_prev_step = _qu.front(); //родитель последняя проверенная
for (int i = 0; i < 4; i++) //четыре направления шага
{
_step = _prev_step;
switch (i) //следующий шаг
{
case 0: _step += 1; break; //вперед
case 1: _step -= 1; break; //назад
case 2: _step += 9; break; //вправо
case 3: _step -= 9; break; //лево
}
//проверки не вышли ли мы за границу
if (_step <= 81 && _step >= 0 && _step % 9 != 0)
//не занята ли клетка, и не проверяли ли мы её
if(!_cells[_step]._isBusy && _explored.find(_step) == _explored.end())
{
_explored[_step] = _prev_step; //добавляем в проверенные
_qu.push(_step); //добавляем в шаги
if (_end == _step)//если дошли до нужной клетки
{
do {
/*
разматываем путь
как мы помним в _explored храниться родитель(в значении)
идя за родителем, мы идем по самому короткому пути.
*/
_reachable.push(_step);
_step = _explored[_step];
//_explored.erase(_explored.end());
} while (_start != _step); //пока не дайдем в начало
return 1;
}
}
}
_qu.pop(); // убираем клетку с которой пришли
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for (int i = 0; i < SIZE; i++) {
cout << "Вершина " << i+1 << ": ";
int path[SIZE], len = 0;
path[len] = i + 1;
len++;
int j = i;
while (j != begin_index) {
for (int k = 0; k < SIZE; k++) {
if (a[j][k] != 0 && d[j] == d[k] + a[j][k]) {
path[len] = k + 1;
len++;
j = k;
break;
}
}
}
for (int k = len - 1; k >= 0; k--) {
cout << path[k] << " ";
}
cout << endl;
}
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
for (int i = 0; i<SIZE; i++) // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
{
int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
2
3
4
5
6
if (v[end]) {
printf("\nОшибка! Вершины 1 и 5 в введенном графе не связаны!\n");
return 0;
}
ver[0] = end + 1; // начальный элемент - конечная вершина
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
{
for (int i = 0; i<SIZE; i++)
{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp < d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex < 10000);
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <stdio.h>
#include <stdlib.h>
#define SIZE 6// количество вершин в нашем графе
int matrix[SIZE][SIZE] = { 0 }; // матрица связей
int a[SIZE]; // посещенные вершины
int d[SIZE]; // минимальное расстояние
int save;//временное хранение различных величин
int begin_index = 0;//задаем индекс начальной вершины, от которой будем искать путь
int min;
int minindex;
void matrix_svyazey()
{
for (int i = 0; i < SIZE; i++)
{
matrix[i][i] = 0;
for (int j = i + 1; j < SIZE; j++) {
printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
scanf("%d", &save);
matrix[i][j] = save;
matrix[j][i] = save;
}
}
}
void Vyvod_matrix()
{
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
printf("%5d ", matrix[i][j]);
printf("\n");
}
}
void alg_kratchayshego_pyti()
{
for (int i = 0; i < SIZE; i++)
{
d[i] = 10000;
a[i] = 1;//отмечает все вершины как необработанные.
}
d[begin_index] = 0;
// Шаг алгоритма
do {
minindex = 10000;//индекс вершины с минимальным весом
min = 10000;// мин вес
for (int i = 0; i < SIZE; i++)
{ // Если вершину ещё не обошли и вес меньше min
if ((a[i] == 1) && (d[i] < min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex != 10000)
{
for (int i = 0; i < SIZE; i++)
{
if (matrix[minindex][i] > 0)
{
save = min + matrix[minindex][i];
if (save < d[i])
{
d[i] = save;
}
}
}
a[minindex] = 0;
}
} while (minindex < 10000);
}
void v_p()
{
int ver[SIZE]; // массив посещенных вершин
int end = 5; // индекс конечной вершины = 6 - 1
ver[0] = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i < SIZE; i++) // просматриваем все вершины
if (matrix[end][i] != 0) // если связь есть
{
int temp = weight - matrix[end][i]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод кратчайших расстояний до вершин
printf("\nkratchayshee rasstoyanie do vershin \n");
for (int i = 0; i < SIZE; i++)
printf("%5d ", d[i]);
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nVyvod kratchayshego pyti\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
}
int main()
{
// Инициализация матрицы связей
matrix_svyazey();
// Вывод матрицы связей
Vyvod_matrix();
alg_kratchayshego_pyti();
// Восстановление пути
v_p();
getchar();
getchar();
return 0;
}
2
3
4
5
6
7
8
9
{
matrix[i][i] = 0;
for (int j = 0; j < SIZE; j++) {
printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
scanf("%d", &save);
matrix[i][j] = save;
}
}
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
int a[SIZE]; // массив посещенных вершинн
int d[SIZE]; // минимальное расстояние
int save;//переменная для временного хранения величин
int begin_index = 0;//задаем индекс начальной вершины, от которой будем искать путь
int min;
int minindex;
void matrix_svyazey()
{
for (int i = 0; i < SIZE; i++)
{
matrix[i][i] = 0;
for (int j = 0; j < SIZE; j++) {
printf("vvedite rasstoyanie %d - %d: ", i + 1, j + 1);
scanf("%d", &save);
matrix[i][j] = save;
}
}
}
void Vyvod_matrix()
{
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
printf("%5d ", matrix[i][j]);
printf("\n");
}
}
void alg_kratchayshego_pyti()
{
for (int i = 0; i < SIZE; i++)
{
d[i] = 10000;
a[i] = 1;//отмечает все вершины как необработанные
//printf("%d %5d", d[i], a[i]);
}
d[begin_index] = 0;
// алгоритм
do {
minindex = 10000;//индекс вершины с минимальным весом
min = 10000;// мин вес
for (int i = 0; i < SIZE; i++)
{
if ((a[i] == 1) && (d[i] < min))
{
min = d[i];
minindex = i;
}
}
// добавляем найденный минимальный вес к текущему весу вершины и сравниваем с текущим минимальным
if (minindex != 10000)
{
for (int i = 0; i < SIZE; i++)
{
if (matrix[minindex][i] > 0)
{
save = min + matrix[minindex][i];
if (save < d[i])
{
d[i] = save;
}
}
}
a[minindex] = 0;
}
} while (minindex < 10000);
}
void v_p()
{
int ver[SIZE]; // массив посещенных вершин
int end = 5; // индекс последней вершины = 6 - 1
ver[0] = end + 1; // начальный элемент - последняя вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес последней вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i < SIZE; i++)
if (matrix[end][i] != 0)
{
int temp = weight - matrix[end][i]; // вес пути из предыдущей вершины
if (temp == d[i])
{
weight = temp;
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // записываем ее в массив
k++;
}
}
}
printf("\n\nkratchayshee rasstoyanie do vershin \n");
for (int i = 0; i < SIZE; i++)
printf("%5d ", d[i]);
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nVyvod kratchayshego pyti\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
}
int main()
{
matrix_svyazey();
// Вывод матрицы связей
Vyvod_matrix();
alg_kratchayshego_pyti();
// Восстановление пути
v_p();
getchar();
getchar();
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
{
for (int i = 0; i < SIZE; i++)
if (matrix[i][end] != 0)
{
int temp = weight - matrix[i][end]; // вес пути из предыдущей вершины
if (temp == d[i])
{
weight = temp;
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // записываем ее в массив
k++;
}
}
}
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
103
104
105
106
107
108
109
110
111
112
113
114
#include <stdio.h>
#include <stdlib.h>
#define SIZE 8
int main()
{
int a[SIZE][SIZE]=
{
{0, 0, 14, 0, 0, 21, 0, 0},
{13, 0, 15, 0, 0, 0, 0, 14},
{14, 15, 0, 12, 0, 0, 13, 0},
{0, 0, 0, 0, 8, 0, 0, 0},
{0, 0, 0, 8, 0, 0, 13, 0},
{21, 0, 0, 0, 5, 0, 0, 0},
{0, 0, 0, 0, 13, 0, 0, 16},
{0, 0, 0, 0, 0, 0, 16, 0},
};
// матрица связей
int d[SIZE]; // минимальное расстояние
int v[SIZE]; // посещенные вершины
int temp, minindex, min;
int begin_index = 0;
system("chcp 1251");
system("cls");
// Инициализация матрицы связей
/*for (int i = 0; i < SIZE; i++)
{
a[i][i] = 0;
for (int j = 0; j < SIZE; j++) {
printf("Введите расстояние %d - %d: ", i + 1, j + 1);
scanf("%d", &temp);
a[i][j] = temp;
}
}*/
// Вывод матрицы связей
for (int i = 0; i < SIZE; i++)
{
for (int j = 0; j < SIZE; j++)
printf("%5d ", a[i][j]);
printf("\n");
}
//Инициализация вершин и расстояний
for (int i = 0; i < SIZE; i++)
{
d[i] = 0;
v[i] = 1;
}
d[begin_index] = 0;
// Шаг алгоритма
do {
minindex = -1;
min = -1000;
for (int i = 0; i < SIZE; i++)
{ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i] > min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
// Добавляем найденный минимальный вес
// к текущему весу вершины
// и сравниваем с текущим минимальным весом вершины
if (minindex !=-1 )
{
for (int i = 0; i < SIZE; i++)
{
if (a[minindex][i] > 0)
{
temp = min + a[minindex][i];
if (temp > d[i])
{
d[i] = temp;
}
}
}
v[minindex] = 0;
}
} while (minindex > -1);
// Вывод кратчайших расстояний до вершин
printf("\nСамое длинное расстояние до вершины: \n");
for (int i = 0; i < SIZE; i++)
printf("%5d ", d[i]);
// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 3; // индекс конечной вершины = 5 - 1
ver[0] = end + 1; // начальный элемент - конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины
while (end != begin_index) // пока не дошли до начальной вершины
{
for (int i = 0; i < SIZE; i++) // просматриваем все вершины
if (a[i][end] != 0) // если связь есть
{
int temp = weight - a[i][end]; // определяем вес пути из предыдущей вершины
if (temp == d[i]) // если вес совпал с рассчитанным
{ // значит из этой вершины и был переход
weight = temp; // сохраняем новый вес
end = i; // сохраняем предыдущую вершину
ver[k] = i + 1; // и записываем ее в массив
k++;
}
}
}
// Вывод пути (начальная вершина оказалась в конце массива из k элементов)
printf("\nВывод самого длинного пути\n");
for (int i = k - 1; i >= 0; i--)
printf("%3d ", ver[i]);
getchar(); getchar();
return 0;
}
2
3
4
5
6
7
{0, 0, 0, 1, 1, 0, 0},
{0, 0, 0, 0, 0, 1, 1 },
{0, 0, 0, 0, 0, 0, 0 },
{0, 0, 0, 0, 0, 0, 0 },
{0, 0, 0, 0, 0, 0, 0 },
{0, 0, 0, 0, 0, 0, 0 }
2
3
4
5
6
7
{1, 0, 0, 1, 1, 0, 0},
{1, 0, 0, 0, 0, 1, 1 },
{0, 1, 0, 0, 0, 0, 0 },
{0, 1, 0, 0, 0, 0, 0 },
{0, 0, 1, 0, 0, 0, 0 },
{0, 0, 1, 0, 0, 0, 0 }
Сейчас граф, который не работает, представлен так, что сверху вниз путь есть, а снизу вверх нету.
2
3
{0, 0, 0 },
{0, 0, 0 }
2
3
{1, 0, 0 },
{1, 0, 0 }
А дальше воспользуйтесь алгоритмом поиска в глубину. Правда, придется его проводить циклически, чтоб найти все пути.
int weight = dist[end] - нужен полный код, чтобы увидеть, где присвоены значения элементов массива dist
var arr=[] - синтаксически некорректная строка
2
3
4
5
6
7
8
{ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]<min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
2
3
4
5
6
7
srand(time(0));
graph = new bool* [size];
for(int i=0; i<size; i++)
for(int j=0; j,size; j++)
if(i==j) graph[i][j] = false;
else graph[i][j] = graph[j][i] = (prob() < 0.19);//for density = 0.19
2
3
4
5
d[i] = 10000;
v[i] = 1;
}
d[0] = 0;
2
system("cls");