Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 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;
}
Результат выполнения
Игра Lines функция поиска короткого пути
дано Одномерный массив _Cells[]
параметр _isBusy(bool) занята клетка или нет
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;
}
И всё таки, как сделать этот алгоритм обратным?
Здравствуйте, такой вопрос, можно ли доработать код, перед началом ввода расстояния, писать сколько у меня будет городов, допустим 3 и ввести их значение. То есть, чтобы мы сами выбирали сколько будет городов с их названиями, ну и расстояние. Буду благодарна за ответ и помощь
SIZE сейчас задана как константа, а Вам нужно сделать переменную
Добрый день. Очень хорошо разобран пример. Программа работает. Единственное, не совсем понятно с последним этапом — вывод кратчайшего пути. У Вас это 1-3-6-5, т.е. до вершины 5. Как я понимаю, в задаче нужно указать кратчайшие пути до всех вершин, т.е. и до 6, и до 4…
Я еще хочу попробовать реализовать этот алгоритм на visual basic.
Строка 74 — индекс конечной вершины
Вставьте следующие строки кода вместо конца программы ( с 97 строчки где зелёным написано //Вывод пути)…
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;
}
Добрый день, подскажите, пожалуйста, имеется ли у вас на сайте статья с Алгоритмом Ли ( Волновым алгоритмом)?
Нет
Добрый день. Возникла проблема. Переделал алгоритм для нахождения кратчайших путей от вершины ко всем остальным вершинам. Но в условии есть такой момент. Кратчайший путь не один. То-есть, допустим мне нужно попасть из точки А в точку Е. Из Из точки А можно попасть точку Б и В, из них в Д, а из неё в Е. Допустим А -> Б = 6, A -> B = 5, Б -> Д = 10, В -> Д = 11, Д -> Е = 4. То-есть 2 кратчайших пути: через Б = 20 и через В = 20. Как вывести оба этих пути?
Как вариант — стирать вес предпоследней вершины для восстановленного пути. И пытаться повторить восстановление пути.
Код пока накидать нет времени. Если кто-то подскажет, буду благодарна
Елена, а можно ли реализовать на C++ (С++Builder) графическую работу с графами? К примеру в окне отображены вершины и связи между ними. Щелчком мыши на линии(графе) нужно "отключить" граф и осуществить поиск пути по оставшимся связям.
Я так понимаю использование LineTo MoveTo не прокатит. Нужен объект, который реагирует на сообщения.
Да, для этой задачи придется создавать собственные объекты. Подробнее не подскажу
Каким образом можно переделать данный алгоритм , чтобы он выводил все возможные кратчайшие пути из одной вершины в другую, если их существует несколько?
Можете ли подсказать, какие изменения внести в алгоритм, чтобы он работал с графами, где не все вершины связаны?
Спасибо!
См. код из моего сообщения в предыдущем треде.
а здесь не все вершины связаны, третья с пятой не связаны. Просто это отображается в таблице связей и всё, разницы никакой
Если в матрице смежности все нули или просто между заданными пунктами нет сообщения, то цикл становится бесконечным. Не подскажете — почему?
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; // начальный элемент — конечная вершина
Граф не обязательно должен быть полностью связанным. Между какой-то парой вершин может отсутствовать связь, и это не мешает работать алгоритму. Но в несвязном графе есть вершины, до которых вообще нет пути. Они-то и мешают работе алгоритма.
Добрый день. Не подскажете как из двумерного массива сделать взвешенный граф
Двумерный массив задаёт матрицу смежности с весами на пересечении каждой пары ребер. Посмотрите тему по способам задания графа
https://prog-cpp.ru/data-graph/
У меня вопрос по поводу восстановления пути, если будет такая ситуация: надо попасть из вершины А в вершину Г, но при этом из вершины А в вершину Б и В одинаковое расстояние, то есть веса Б и В будут совпадать, но В не ведет в вершину Г, а Б ведет. Получается алгоритм пойдет по пути который раньше встретится в массиве?
Алгоритм пройдёт по всем путям и выберет кратчайший. Порядок обхода лексикографический, то есть в Б мы попадем раньше, чем в В.
Всё доступно и понятно,мне нравится.
Задача комивояжера: Обойти все города определив кротчайший путь (Алгоритм Дейкстры)
∞7 0 1 4
6 ∞4 7 0
0 6 ∞0 6
2 5 0 ∞5
5 0 3 2 ∞
Классно очень ясно и понятно мне понравилось
Подскажите, пожалуйста, а как найти несколько кратчайших путей?
так же, как и один
Добрый день, сразу выражаю благодарность за столь понятные примеры, учу си буквально по вашему сайту. Однако есть вопрос, как в данном алгоритме реализовать проверку для заведомо недоступной вершины? Скажем если будет вершина, до которой нельзя добраться из начальной, то выводило бы на месте расстояния до нее "-1"?
Когда найдены все пути, и очередь кончилась, проверить те вершины, у которых сохранился максимальный (начальный) вес. Значит, их достичь не удалось
А если сложится так, что их вес и есть максимальный?
Вес, который присваивается изначально всем вершинам, должен быть больше суммы всех весов графа
Понял, благодарю!
здравствуйте, а как с помощью вашего примера мне найти кратчайший путь из вершины k к вершине p когда: n=6 k=1 p=6
begin_index отвечает за начальную вершину. Из нее ищется кратчайший путь до всех остальных
А если отсчет нужно будет начинать не с первой вершины а например с 4?
Для нее нужно будет обнулить начальный вес
А как это сделать?
Строчка 38 и строчка 11.
Задать начальную вершину в begin_index
Здравствуйте, объясните пожалуйста эти строчки
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);
51-53 строка — комментарии к данному фрагменту кода
Здравствуйте, подскажите пожалуйста, как сделать еще и считывание исходных данных с файла здесь? Заранее спасибо.
https://prog-cpp.ru/c-files/
Посмотрите работу с файлами
У меня вопрос по реализации алгоритма. В описании задачи указано что данный алгоритм подходит для нахождения кратчайшего пути в сетях, где есть одностороннее движение. Но при инициализации матрицы связей
for (int i = 0; i<SIZE; i++)
{
a[i] = 0;
for (int j = i + 1; j<SIZE; j++) {
printf("Введите расстояние %d — %d: ", i + 1, j + 1);
scanf("%d", &temp);
a[j] = temp;
a[j] = temp;
}
}
Отсутствует возможность указать что есть дорога из a[j] в a[j], но дороги из a[j] в a[j] нет. Получается что данное реализация уже на этапе инициализации предусмотрена только для неориентированных сетей.
Инициализация взята для примера. В случае ориентированного графа нужно задать все расстояния, а не только верхний треугольник матрицы (с дублированием в нижний)
Добрый день!
Хотел бы обратить внимание, что в объяснении алгоритма у Вас в одном месте неправильно выставлены знаки препинания, и это изменяет смысл фразы. Может сбить с толку человека, который впервые знакомится с решением через данный текст.
Вот отрывок второго абзаца пункта "Первый шаг:
"Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значению её метки, и длины ребра, идущего из 1-й в 2-ю…"
Здесь по вашей записи "значение её метки" — получается как второе слагаемое из трех. А на самом деле это просто уточнение насчёт первого и слагаемых всего 2: расстояние до вершины 1 и длина ребра.
Поэтому рекомендую поставить вместо запятых скобки, и всё сразу станет понятно:
"Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки), и длины ребра, идущего из 1-й в 2-ю…"
А вообще, замечательная статья. Спасибо Вам!
Да, сам лишнюю запятую поставил от спешки) Извиняюсь. Должно быть так:
"Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й в 2-ю…"
Здравствуйте, я переделала код через функции, помогите пожалуйста, как в его можно изменить для ориентированного
то есть все поже самое, но идти можно только в одну сторону
я еще новичок, можно подробно, пожалуйста
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;
}
как здесь нормально загрузить программу?
я заменила a[size] на a[size]={0}
набрала строчку а[j] = temp;но у меня теперь вообще но показывается в консоли
вывод кратчайшего пути
Я вручную форматирую программу при одобрении комментариев.
На сайте предложен код, который работает и с ориентированным, и с неориентированный графом
получается ребро 12 можно обозначить, а ребро 21 никак нельзя, хотя в графе как раз например нужен путь именно из 21, как сделать так, чтобы можно было отметить все пути?
я пробовала в 18 строчке for (int j = i + 1; j<SIZE; j++) {
сделать int j = 0; j<SIZE; j+
но тогда в кратчайшем пути появляется первая и последняя вершины
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;
}
Ошибка в строчках 86, 88.
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 }
Странно, очень странно…
А путь откуда куда?
Как от 0 до 1 и 2 не работает, так и от 1 и 2 до 0.
2
3
{1, 0, 0 },
{1, 0, 0 }
А вот так всё работает. Пробовал вместо единичек разные значения ставить, тоже в каких-то случаях не проходил до конца.
Исправила ошибку в статье. Теперь будет работать восстановление пути и для ориентированных графов.
Получается вершины если в графическом виде представлять, начинаются с 0 и рассчитывается тоже с 0;
Здравствуйте, не совсем понял, почему индекс конечной вершины end изначально равен 4, ведь вершин 6, то есть end должен равняться 5.
Потому что мы решили искать кратчайший путь до 5 вершины. Можем искать до любой.
Добрый день, возникла похожая проблема. Хочу найти кротчайший путь от 1 до 6 вершины, поменял 4 на 6 в end, но ничего не изменилось, алгоритм всё равно находит путь до 5 вершины, а не до 6, подскажите пожалуйста как исправить
Из индекса искомой вершины вычитается 1
Здравствуйте, Елена. Очень доступно вы обяснили алгоритм Дейкстры. Спасибо огромное! У меня к вам просьба. Может быть вы обясните мне как решить следующую задачу.
Есть масив отрезков прямых линий.Отрезки не пересекаются. Если соприкасаются, то только в начале или конце отрезка.Также может существовать несколько идентичных отрезков, накладываемых друг на друга.
Необходимо упорядочить их так, чтобы можно было сделать трассировку по всем отрезкам, в том числе и по идентичным — без пропусков. Если это невозможно, тогда найти наибольшее количество отрезков соединенных между собой. Спасибо.
А идентичные отрезки учитываются как один или каждый сам за себя?
Нет. Это не один и тот же отрезок. По нему тоже необходимо сделать трассировку.
Представьте свой массив отрезков в виде графа, где координаты начала и конца — вершины, а сами отрезки — ребра.
А дальше воспользуйтесь алгоритмом поиска в глубину. Правда, придется его проводить циклически, чтоб найти все пути.
Спасибо за ответ. Но это будет очень трудоемкий процесс. Ведь поиск нужно проводить с каждой отдельной вершины. А отрезков может быть и 100000 и больше. Может быть есть другое решение?
Простите, а как сделать так чтобы выводилась последовательность вершин, определяющая кратчайший путь не до фиксированный вершины, а до всех вершин?
В строке 77 назначить нужную вершину и повторить восстановление пути требуемое число раз.
А зачем в 77 строке назначать вершину? Там же конечная вершина( та до, которой нужно найти путь), а мне нужно до всех вершин графа
Значит, сделать цикл и все по очереди назначить
Здравствуйте, а где прописано, что начальная вершина это 1 и можно ли сделать так, чтобы пользователь сам выбирал начальную вершину?
Начальная вершина задается в begin_index
Здравствуйте! Если в begin_index для указанного примера поместить значение 4 (то есть, в качестве начальной вершины взять вершину 5) то путь до вершины 1 рассчитывается неверно, точнее, выводится не самый кратчайший. Подскажите, пожалуйста, с чем это связано.
Ошибки не вижу
Прошу прощения, допустила ошибку в коде, все верно
Как именно можно из этого алгоритма сделать поиск наибольшего пути? В каком месте кода и что именно изменить?
Начальные значения вместо 10000 взять 0 и поменять условие < на > в 45 строке
Сделал, как вы указали. Не работает.
Без кода ничего не скажу. Я же не вижу, что изменилось в программе.
Как можно найти кратчайший путь до точки я понял, а вот про критический путь ничего не сказано. Как можно найти критический путь?
Кратчайший-это и есть критический.
Коллеги, а можно ли как-то модифицировать чтобы вывести все пути между двумя заданными вершинами (то есть не только критический путь, а так же остальные), ну или между всеми вершинами графа.
Два онлайн компилятора ошибки находят
https://www.onlinegdb.com/online_c++_compiler
http://cpp.sh/
main.cpp: In function ‘int main()’:
main.cpp:77:11: error: storage size of ‘ver’ isn’t known
int ver[]; // массив посещенных вершин
^
main.cpp:81:16: error: ‘dist’ was not declared in this scope
int weight = dist[end]; // вес конечной вершины
^
main.cpp:82:1: error: ‘var’ was not declared in this scope
var arr =[]
^
Пока ничего удивительного не вижу.
int ver[]; не указан размер массива
int weight = dist[end] — нужен полный код, чтобы увидеть, где присвоены значения элементов массива dist
var arr=[] — синтаксически некорректная строка
Как сделать, чтобы пользователь вводил точку графа и до неё считался кратчайший путь? В статье от 1 и до следующей, а так надо чтобы в консоле вводит пользователь например 4 и вводил координаты до 4 точки, чтобы она была началом, но чтобы не в коде сам менял, а через консоль
Спасибо!
Спасибо за труд. Всё расписано и понятно.
Здравствуйте, в вашем алгоритме реализованы кратчайшие пути от первой вершины до всех остальных,т.е. от первой до первой , от первой до второй, от первой до третьей,от первой до четвертой и от первой до пятой , а как сделать так,чтобы находило автоматически для всех вершин пести до всех остальных, например , кратчайшие пути от второй вершины до первой,второй,третьей, и т.д., потом кратчайшие пути от третьей до первой ,второй ,третьей и т.д. , и так до пятой вершины , чтобы как бы создать матрицу расстояний
В строчке 38 обнулить вес для той вершины, из которой нужно найти путь до всех остальных. Для этого в 11 строке указать номер начальной вершины.
Программа уходит в вечный цикл, если я пишу, например, d[1] = 0;
В код примера внесла поправки. Теперь номер начальной вершины задается в строке 11.
Я ознакомился с комментариями выше, сделать ориентированный граф вышло, но вот вывести путь кратчайший до той вершины, которая дана по условию задания у меня не вышло. Вам будет трудно оставить код по выводу кратчайшего пути от одной заданной вершины до другой? Также интересен следующий вопрос.. если я хочу от условно 2 вершины до 5, узнать кратчайший путь и длину, то надо менять в 38 строке элемент по индексу 3, присваивая его 0?
Нужно перед поиском кратчайшего пути поменять местами вершины графа в матрице так, чтобы отправная вершина 2 оказалась начальной.
Здравствуйте, не могли бы Вы подсказать, как сделать так, чтобы размер матрицы задавался пользователем в консоли?
Используйте Динамическое выделение памяти
Здравствуйте, как сильно нужно изменить алгоритм, чтобы он работал для ориентированного взвешенного графа? Ведь если пытаться использовать именно этот алгоритм, то в определённых ориентированных графах будет ответ, как будто он неориентированный, т.е другой.
См.комментарии выше
Здравствуйте. Я не понимаю такой момент. Ведь мы сначала присваиваем бесконечно большой вес всем вершинам. Зачем мы потом опять присваиваем бесконечно большое число minindex и min?
А как иначе делать первое сравнение в 45 строке? Эти переменные должны уже иметь какое-то значение.
2
3
4
5
6
7
8
{ // Если вершину ещё не обошли и вес меньше min
if ((v[i] == 1) && (d[i]<min))
{ // Переприсваиваем значения
min = d[i];
minindex = i;
}
}
Как это работает если min у нас 10000 и все d=10000, условие же не сработает
Исходно значение min выбирается больше всех вычисленных с тем, чтобы заменить его на меньшие значения в цикле.
давайте в контакте поговорим насчет графов
Здравствуйте! А как найти длину максимального пути и сам путь? Есть ли алгоритм?
Поменять условие с «меньше» на «больше»
Здравствуйте! Правильно ли я понимаю, что данный алгоритм предназначен для поиска кратчайших путей от известной вершины до ВСЕХ? А какой алгоритм выбрать, если нужно найти кратчайший путь между двумя данными вершинами? Подойдет ли тут, например, волновой алгоритм? Заранее спасибо!
Можете использовать этот же алгоритм, и прекратить поиск как только достигнете требуемой вершины
Спасибо, Елена. Не могли бы подсказать следующее. Если я решу воспользоваться волновым алгоритмом, то смогу ли реализовать его для взвешенного неориентированного графа?
Думаю, да.
Здесь есть описание волнового алгоритма, но для невзвешенного графа
https://prog-cpp.ru/data-graph/
Доброго дня, Елена! А что нужно поменять в вашем алгоритме, чтобы поиск осуществлялся от верхнего левого значения в матрице до нижнего правого. Заранее благодарен
В 77 строчке задать индекс конечной вершины
Приветствую, меняется ли алгоритм существенно, если весы будут принимать отрицательные значения
Зависит от условия задачи, допускается ли отрицательная длина пути.
Здравствуйте. Я убрал 22-ую строку, чтобы граф стал ориентированным, но при этом перестал выводиться кратчайший путь. Что нужно еще изменить в коде чтобы он выводился?
В строке 18 сделать полный цикл для j от 0 до SIZE
Немного неточно выразился. Мне нужно, что всё было как в этом коде за исключением симметричности. То есть ввожу всё так же, но чтобы всё, что ниже нулевой диагонали, тоже было равно нулю. Заранее спасибо
Тогда нужно исходно обнулить все элементы массива а.
Строка 7:
«int k = 1; // индекс предыдущей вершины»
Подскажите пожалуйста, предыдущая вершина это какая?
Та, из которой осуществляется переход в текущую
Дякую вам за вашу працю!
Уважаемая Елена,
спасибо за данную статью и вообще за Вашу просветительскую работу в направлении компьютерных наук! В России эта сфера всегда будет испытывать дефицит в методических материалах на русском языке, равно как и в специалистах, способных создавать качественное ПО. Касательно самой статьи — как Вы считаете, имеет ли смысл несколько изменить программный код таким образом, чтобы граф создавался автоматически случайным образом? Что-то типа:
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
Спасибо.
Это уже на усмотрение читателя 🙂
Здравствуйте.
Это единственная статья про алгоритм Дейкстры? Меня интересует алгоритм Дейкстры, реализованный на основе d-кучи. В поиске на текущем сайте не нашёл.
На текущий момент на этом сайте — единственная
А что значит переменная temp?
Используется для временного хранения различных величин внутри циклов
И вот эти строчки, не могу понять их(
2
3
4
5
d[i] = 10000;
v[i] = 1;
}
d[0] = 0;
Исходное всем вершинам присваивается бесконечно большой вес (массив d), чтобы потом этот вес уточнять. Массив v отмечает все вершины как необработанные.
Спасибо большое, с помощью статьи смог объяснить студентам, как правильно делать.
Здравствуйте. Не подскажете за что отвечают переменные minindex и min?
min — это минимальный вес, а minindex — индекс вершины с минимальным весом
Добрый день, появился еще вопрос. Вот большой цикл, который на строчках 40-67, как его можно заменить его условие при измене этого цикла на эквивалентный ему while () { … }? Ибо, если так и оставить (minindex<10000), компилятор ведь даже не зайдет в цикл. Подскажите, пожалуйста.
Не поняла вопроса. А чем цикл с постусловием do…while не устроил? Да, цикл while() может не выполниться ни разу. Для этого и используется цикл с постусловием.
Елена, извините, немного не понятно с конечным выводом. Для чего мы снова выводим матрицу связей? Разве мы не должны вывести кратчайшее расстояние? Заранее спасибо за ответ!
Спасибо за замечание. Действительно, мы выводим вектор полученных кратчайших расстояний до вершин. Ошиблась в комментарии.
Спасибо большое за ответы
А вы не подскажите как поступить с ориентированым графом? Как при это меняется матрица?
Если граф ориентированный, то матрица перестанет быть симметричной. В этом случае строки будут представлять собой исходящие вершины, а столбцы — входящие.
То есть SIZE регулирует до какой вершины я хочу добраться? Допустим, если из 1й вершины в 3-ю, то вместо SIZE я должен поставить 3?
Нет, SIZE — это количество вершин графа. А кратчайшие пути до всех вершин (из первой) по завершении алгоритма формируются в массиве d. Если нас в качестве исходной интересует другая вершина, то мы всегда можем поменять строки и столбцы матрицы так, чтобы исходная вершина оказалась на первом месте.
Вы не так меня поняли. Меня интересует как самому выбрать от какой вершины и до какой я хочу найти минимальное расстояние и вывести эти вершины
Сам алгоритм — это строки с 37 по 67 примера. При желании Вы можете его вынести в отдельный метод. В результате формируется вектор d, который содержит кратчайшие пути до всех вершин из первой рассматриваемой вершины.
А матрицу, в которой Вы ищете кратчайший путь, Вы задаёте сами.
Вы могли бы приложить код, просто еще только начал работать то стеком и не совсем разбираюсь. Буду очень благодарен
Код находится в тексте статьи. Можете его скопировать.
а как сделать чтобы можно было ввод с файла
Посмотрите здесь
Как программным путём вывести путь(то есть через какие вершины нужно идти от 1-2, 1-3 и т.д.). Допустим от 1 до 4, можно пойти через 2 и 3 как вывести в коде что бы показать что мы пошли именно через 2 вершину?
При обходе графа необходимо создать стек, куда помещать все «пройденные» рёбра в виде структуры «начало-конец».
После того, как требуемая вершина достигнута, извлекаем из стека последнее ребро (с концом в этой вершине) и переходим к началу этого ребра и сохраняем эту вершину.
Теперь, последовательно извлекая из стека рёбра, необходимо определить, как мы попали в эту сохранённую вершину. И так далее, пока не дойдём до начала.
Таким образом, мы получим весь найденный путь, но от конца к началу. Если необходим путь от начала к концу, то нужно воспользоваться еще одним стеком.
математическое толкование есть этому?
Здравствуйте, подскажите, пожалуйста, а как реализовать в коде, чтобы можно было вводить количество вершин? Заранее благодарю
Через динамическое выделение памяти.
я не это имел в виду, а то как по алгоритму сделать вывод о выборе пути. Например чтобы из 1 попасть в пятую нужно мысленно встать в пятую вершину и идти к той у который минимальный вес. Таким образом получаем 5-6-3-1. Следовательно наш искомый путь 1-3-6-5. Я пропустил один пункт в объяснении но поскольку я не уверен что вообще прав дождусь вашего ответа
Совершенно верно. Путь ищется в обратном направлении, то есть в вершину 5 мы попали из вершины 6. Здесь только критерий — не минимальный вес предыдущей вершины, а минимальный вес суммы предыдущей вершины и дуги к текущей.
То есть в данном случае из вершины 5 мы выбираем обратный путь как min(11+9, 20+6).
Забыли описать самое главное. А как определить через какие вершины идти минимальным путем, например, из первой в пятую. Объясните пожалуйста
Спасибо за замечание, исправила в тексте статьи.
Спасибо, очень доступно и понятно!!!
Для хранения весов графа используется квадратная матрица
расшифруйте матрицу.
Добавила расшифровку в текст статьи.
Помогите, зачем эти две строчки?
2
system("cls");
Это для того, чтобы русскоязычные символы корректно отображались в окне консоли.
system("chcp 1251"); // изменение кодовой страницы на 1251
system("cls"); // очистка экрана
В википедии при разрисовке данного графа содержится ошибка, каким образом на 4-м шаге, из 6-й посещенной вершины, мы попадаем в 4-ю?
Да, вес у вершин 4 и 5 одинаковый, но это противоречит физическому смыслу, если представить, что вы находитесь на развилке дорог.
Порядок вершин должен быть по идее … 6, 5, 4.
В данном случае решается задача поиска кратчайшего пути из вершины 1 в каждую из других вершин. Поэтому для обработки будет выбрана вершина с наименьшим весом, а в случае одинаковых наименьших весов — с наименьшим индексом.
даа классная, есть о чем подумать)))
классная статья все подробно описано и доступно а главное понятно