Кратчайшее время в пути от источника до пункта назначения

Рассмотрите список станций, скажем, 10 станций, от «A» до «J», соединенных между собой поездами.Кратчайшее время в пути от источника до пункта назначения

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

ПРИМЕЧАНИЕ: Я упоминаю график только для понимания. О нем можно было подумать.

Проблема: Учитывая любые две станции и время начала от начальной станции, как найти кратчайшее время к месту назначения, отсчет времени ожидания между прибытием и отъездом в случае перелетов? И что DS будет использоваться для того же самого? Предположим, что если две станции соединены поездом, то между ними только один и только один поезд.

источник

2016-03-23 Subhajit Kundu

Только для иллюстрации, предположите поезд между 'C' и 'D'. Также предположим, что вы можете прийти к «C» из «A» или «B». Время ожидания на станции «C» для поезда до «D», таким образом, зависит от того, достигли ли вы «C» от «A» или «B». Однако время в пути от «C» до «D» одинаково независимо от того, как и когда вы прибыли на «C». –

https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm => Предполагая, что время перехода одной станции на другую не равно. – Mukit09

@ MukitChowdhury - Dijkstra здесь недостаточно, из-за этих «прыжков». – libik

IMHO Dijkstra должно быть достаточно в конце концов.

Если вы запустите Dijkstra из узла «A», он найдет самый короткий путь ко всем другим узлам.

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

Единственное отличие в том, что вы считаете цену, как «время ожидания + время путешествия» вместо того, чтобы только «время путешествия»

Такого поведения вызваны поездами, имеющими реальный «прибытие/вылет».

Если каждый маршрут для каждого узла A2 в каждой комбинации узлов A1 -> A2 -> A3 получает случайное наказание за переход от A1 до A3 через A2, то это будет непредсказуемо, я думаю.

источник

2016-03-23 10:50:22 libik

Нет! Дийкстра - не ответ. Рассмотрим «A», «B» и «J» с источником = 'A' и dest = 'J'. Рассмотрим, что «A» соединен с «J» поездом в Утро 6 и занимает 2 часа. Рассмотрим, что «A» соединен с «B» поездом в 12 часов в полдень, и он принимает 3 часа, а «B» подключается к «J» в 6 вечера, и это занимает 3 часа снова. Если путешественник стартует в 5 утра, то «А» - «J» является самым коротким. Однако, если путешественник стартует в 10:00, он может достигнуть «J» через «B» и добраться до пункта назначения через 11 часов. Поскольку мы хотим минимизировать общее время, таким образом, этот маршрут является самым коротким для него/нее. –

@SubhajitKundu - это то, что решил Дийкстра решить. «Цена» - это общее количество часов - ожидание и время в пути. Если вы начинаете в 10:00, то самый короткий путь - A -> B, что означает «2 часа ожидания + 3 часа в пути = 5 часов», поэтому он будет первым. Затем вы снова измеряете «общее количество часов» для B -> J, что будет стоить меньше, чем A -> J. – libik

@SubhajitKundu - единственное различие заключается в том, что вам приходится подсчитывать цену, каждый раз, когда вы приходите куда-нибудь как точное время прибытия. Только немного сложнее, но никаких изменений в самой дикшне вообще. – libik

Кратчайшее время в пути от источника до пункта назначения

ответ

Смежные вопросы