Кратчайший путь между городами, где вы можете воспользоваться поездом или автобусом DYNAMI C ПРОГРАММИРОВАНИЕ

Question

есть проблема, которая сводит меня с ума!

- это должно быть решено с помощью динамического c программирования btw -

У меня 80 городов, и есть дополнительный стартовый город для поездки. Мне нужно найти кратчайший путь к каждому из этих 80 городов из одного города. Но проблема в том, что путешественник может воспользоваться автобусом или поездом.

Во входных данных информация о том, существует ли железнодорожный путь между двумя указанными c городами, если между указанными c городами существует автобусная линия, среднее время в пути для путешественника, который использует один из этих вариантов, а также будет указано среднее время в пути между автовокзалом и железнодорожным вокзалом в городе, если оно есть. Во время поездки в конкретный город c мы можем изменить наш вариант перевозки не более одного раза.

Я думаю, что я могу абстрагировать эту проблему до уровня, что каждый город является вершиной, и поскольку эта структура не может быть ациклическим c графом; Я могу использовать такой алгоритм, как Беллман-Форд, или другой алгоритм, который выполняется за время O (VE). Но между двумя городами может быть 2 ребра, одно для автобуса и одно для поезда. Тогда я понятия не имею о том, как я мог справиться с этим. Таким образом, рекурсия будет зависеть от 2 параметров, назначенной вершины и максимального количества ребер, которые должны достигнуть этого города. Но здесь, я думаю, у меня есть еще один параметр, касающийся этой проблемы, связанной с поездом-автобусом, с которым я понятия не имею, b c, поскольку, как я уже говорил, мы можем изменить наш транспорт не более одного раза во время путешествия.

Моя проблема просто если есть два города, в которых мы можем изменить наш способ транспортировки на протяжении всего пути, изменение варианта перевозки в первом возможном городе из-за более низкой стоимости может не привести к наименьшей общей стоимости, поскольку, возможно, изменение варианта перевозки во втором возможном город снижает стоимость больше, чем первый город снижается.

Любая помощь будет оценена. Заранее спасибо!

Answer 1

Допустим, у вас есть только опция шины, для решения которой вы можете использовать Dijkstra's algorithm, которая обычно используется для поиска пути от одного узла к другому, но может быть легко изменена для поиска кратчайший путь ко всем узлам графа. Мы действительно возьмем каждый город за узел, а за каждую полосу - за край, и мы закончили:)

Теперь интересная часть: когда вы можете переключаться между поездом и автобусом только один раз. Давайте создадим два графика, G_b и G_t, где G_t содержит только пути поездов, а G_b содержит только пути автобусов, а веса - это время в пути. Следующий шаг - соединить одним направленным ребром все узлы от G_b до соответствующего узла в G_t. Создайте еще одну копию этого графика, но на этот раз подключите G_t к G_b.

Теперь запустите Dijkstra's algorithm на этих двух графиках. Если вы хотите узнать, какое время было самым коротким для указанного c города - возьмите минимум из всех 4 вхождений этого города.
Вы можете узнать, изменили ли мы транспорт, проверив, изменили ли мы слой на графике.

Сложность по времени намного ниже, чем у Беллмана-Форда, поскольку мы только дважды запускали алгоритм Дейкстры. O(E + V log V)

Answer 2

Вместо того, чтобы делать каждый город узлом, вы можете сделать так, чтобы каждая автобусная остановка, а также каждый поезд останавливали узел, и имели ребра между соседними автобусными остановками и соседними остановками поездов, а также между автобусными остановками и остановками поездов. в тех же городах. Затем вы можете запустить какой-нибудь алгоритм SSSP, возможно, Dijkstra, который работает намного быстрее, чем Bellman-Ford, и работает для графиков acycli c (при условии, что нет отрицательных граней) из исходного города.

Чтобы гарантировать, что вы не меняете метод транспортировки более одного раза, вы можете добавить дополнительный логический параметр для каждого состояния, который показывает, изменили ли вы метод транспортировки в какой-то момент ранее.