БлогNot. Комментарии к статье #1330 (1-3)

C++: поиск кратчайшего пути на графе


Комментарии отсортированы по убыванию даты, нажмите сюда, чтобы отсортировать их по возрастанию даты


Автор: Sasha IP: определён

Почему сам поиск не может зациклиться например на 0-1-4-2-0-1-4-2-0 дорогах? Как происходит обход зацикливания? И как делается шаг назад если например из пути 2-3 больше нет прохода в 7? Если взять любые другие данные, почему машина определит что путь по сумме цифр 8, будет лучше чем путь по сумме цифр например 11, хотя для 1 случая он может пройти 5 вершин а для второго 4 вершины?

23.01.2020, 14:26

Ответ: Смотри исходники, каждое действие закомментировано. Пройденные вершины помечаются в incl. "Шаг назад" в step (массив road) Путь ищется самый короткий именно в смысле суммы весов, такова задача.


Автор: Alex IP: определён

Можете пожалуйста написать, как выглядел бы этот участок кода, если бы у нас была бы не структура,а просто матрица с нулями и единицами? int find (int s, int c) { //вес пути из s и c или 0, если пути нет for (int i=0; i<m; i++) if (map[i].s==s && map[i].c==c || map[i].s==c && map[i].c==s) return map[i].v; return 0; }

08.01.2019, 18:33

Ответ: Метод find просто возвращает вес пути от одного узла к другому, если бы данные "лежали" в матрице A, вместо вызова метода мы могли бы писать в двойном цикле (по i и по j) w = A[i][j];
Но в случае такого представления данных изменится и многое другое в проге :)
Мне как раз структуры кажутся лучше и менее избыточными для такой задачи.


Автор: Валерий IP: определён

Никак не пойму, как относятся к графу цифры из структуры. struct item map[m] = { //все пути, нумерация узлов с нуля {0,1,1}, {0,2,1}, {2,3,1}, {1,4,1}, {2,4,1}, {4,5,1}, {4,7,1}, {5,6,1}, {6,7,1} }; эти цифры не связаны ничем на графе

12.05.2018, 18:12

Ответ: {0,1,1}, {0,2,1} - означает именно, что вершина 0 связана с вершинами 1 и 2, как на картинке, веса обеих связей (третьи числа в списках) приняты для простоты за единицу, как написано в тексте, но алгоритм должен работать и при других весах