|
Задано N городов-вершин графов. Ребра графа-время на дорогу. Подскажите, пожалуйста, по какому алгоритму можно вычислить минимальный путь(не минимальное расстояние, а именно минимальный путь). т.е. программа должна указать маршрут, по которому следует двигаться. задан 10 Май '13 22:46 
Андрей Алексеев |
|
Есть известный алгоритм Дейкстры. Он позволяет находить не только кратчайшее расстояние между точками, но и строить кратчайший путь. Нужно для каждой точки запоминать не только длину кратчайшего пути, но и сам путь минимальной длины (например, в виде последовательности проходимых рёбер). Когда происходит сравнение длин путей, то из двух путей оставляем самый короткий, и на каждом шаге алгоритма храним все эти данные в памяти. Добавление. На самом деле, здесь пути запоминать не обязательно. Достаточно оценок на вершинах. Если нас интересует кратчайший путь из $%u$% в $%v$%, то по этим числам мы, вообще говоря, не знаем, куда надо двигаться из $%u$%. Однако возможно восстановление кратчайшего пути в обратную сторону. Мы знаем оценку вершины $%v$%, а также оценки соседних с ней вершин вместе с весами рёбер. Надо найти такую вершину, для которой её оценка в сумме с весом ребра, идущего в $%v$%, равна оценке вершины $%v$%. Такая вершина существует по построению, и в неё надо пройти, восстанавливая тем самым кратчайший путь до $%u$%. отвечен 10 Май '13 23:15 
falcao |
|
на емаксе внизу есть код с запоминанием предков Есть еще алгоритм работающий и с отрицательными ребрами: Алгоритм Беллмана — Форда Еще если веса небольшие можно разбить ребра на кучу ребер(для веса n - n ребер) и посчитать BFS'ом отвечен 12 Май '13 0:14 
algogol |
Надо точнее сформулировать условие. У Вас не сказано, откуда и куда надо двигаться.
@falcao, это будет задано пользователем
Я так и подумал, что имелся в виду путь между двумя заданными точками, поэтому написал ниже про алгоритм Дейкстры.