алгоритм Дейкстры с доп.условием , неориентированные графы

[Akina]

Цитата m-ch @ 01.07.22, 06:01

3. По найденному маршруту определяем минимальный вес в маршруте, это и будет ограничение поезда из одного города в другой

Вот как-то неочевидно.
Минимальное остовное дерево минимизирует именно вес всего дерева, а не максимальную стоимость ребра этого дерева. Аналогично-обратно и для максимального дерева.

Цитата m-ch @ 01.07.22, 06:01

при этом вес поезда будет не менее уже определенного

Вот! сам говоришь - не меньше! Значит, может быть и больше? А значит, может быть и более одного маршрута, где больше, и у них эти "больше" могут быть разными. И тот, у которого будет самое большое "больше" (да и вообще требующийся в задаче путь), не обязан быть кратчайшим.

Добавлено 01.07.22, 10:07

В теории задача решается экстенсивно (не знаю как будет с производительностью).

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

Сообщение отредактировано: Akina - 01.07.22, 10:14

[Majestio]

FasterHarder, посмотри видосик - возможно тебя это заинтересует.

[Квант]

Цитата FasterHarder @ 28.06.22, 02:58

Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.
Это случаем не построение остова, только не минимального, как принято, а максимального? + при этом фактор протяженности вообще не играет никакой роли, как понимаю, нужно смотреть ТОЛЬКО на тоннаж.
Или есть какое-то стандартное название алгоритма для такого задания?

Получилось решить?
Фактор протяженности влияет, но и дополнительное условие есть.
Насколько знаю, такая задача называется - Constrained Shortest Path First