Задано N городов-вершин графов. Ребра графа-время на дорогу.

Подскажите, пожалуйста, по какому алгоритму можно вычислить минимальный путь(не минимальное расстояние, а именно минимальный путь). т.е. программа должна указать маршрут, по которому следует двигаться.

задан 10 Май '13 22:46

изменен 12 Май '13 0:11

Deleted's gravatar image


126

Надо точнее сформулировать условие. У Вас не сказано, откуда и куда надо двигаться.

(10 Май '13 22:54) falcao

@falcao, это будет задано пользователем

(10 Май '13 23:25) Андрей Алексеев

Я так и подумал, что имелся в виду путь между двумя заданными точками, поэтому написал ниже про алгоритм Дейкстры.

(11 Май '13 0:00) falcao
10|600 символов нужно символов осталось
5

Есть известный алгоритм Дейкстры. Он позволяет находить не только кратчайшее расстояние между точками, но и строить кратчайший путь. Нужно для каждой точки запоминать не только длину кратчайшего пути, но и сам путь минимальной длины (например, в виде последовательности проходимых рёбер). Когда происходит сравнение длин путей, то из двух путей оставляем самый короткий, и на каждом шаге алгоритма храним все эти данные в памяти.

Добавление. На самом деле, здесь пути запоминать не обязательно. Достаточно оценок на вершинах. Если нас интересует кратчайший путь из $%u$% в $%v$%, то по этим числам мы, вообще говоря, не знаем, куда надо двигаться из $%u$%. Однако возможно восстановление кратчайшего пути в обратную сторону. Мы знаем оценку вершины $%v$%, а также оценки соседних с ней вершин вместе с весами рёбер. Надо найти такую вершину, для которой её оценка в сумме с весом ребра, идущего в $%v$%, равна оценке вершины $%v$%. Такая вершина существует по построению, и в неё надо пройти, восстанавливая тем самым кратчайший путь до $%u$%.

ссылка

отвечен 10 Май '13 23:15

изменен 11 Май '13 16:05

10|600 символов нужно символов осталось
2
ссылка

отвечен 11 Май '13 10:20

10|600 символов нужно символов осталось
0

на емаксе внизу есть код с запоминанием предков

Есть еще алгоритм работающий и с отрицательными ребрами: Алгоритм Беллмана — Форда

Еще если веса небольшие можно разбить ребра на кучу ребер(для веса n - n ребер) и посчитать BFS'ом

ссылка

отвечен 12 Май '13 0:14

изменен 12 Май '13 0:20

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×824
×322
×265
×75

задан
10 Май '13 22:46

показан
2753 раза

обновлен
12 Май '13 0:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru