У меня проблема с поиском самого быстрого пути, который не превышает указанной стоимости. Есть аналогичный вопрос к этому, однако между ними есть большая разница. Здесь в данных могут появиться только те записи, которые ведут от более низкой точки к более высокой точке (например, 1 -> 3 может появиться, а 3 -> 1 может не появиться) (см. ниже). Не зная этого, я бы использовал Дейкстру. Эта дополнительная информация может позволить ему работать быстрее, чем алгоритм Дейкстры. Что вы думаете об этом?
Допустим, у меня указана максимальная стоимость и 4 записи.
// specified cost
10
// end point
5
//(start point) (finish point) (time) (cost)
2 5 50 5
3 5 20 9
1 2 30 5
1 3 30 7
// all the records lead from a lower to a higher point no.
Я должен решить, возможно ли добраться из точки (1) в (5) (это невозможно, когда нет пути, который стоит ‹= чем у нас есть, или когда нет связи между 1-5) и если да, то что будет самый быстрый способ попасть туда.
Выход для таких данных будет:
80 // fastest time
3 1 // number of points that (1 -> 2) -> (2 -> 5)
Имейте в виду, что если есть запись о том, что вы можете перемещать 1->2
1 2 30 5
Это не позволяет вам перемещаться 2‹-1.
