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

[FasterHarder]

Всем хай! Сходу к делу!

Условие такое.
Есть города, которые связаны двусторонней железной дорогой ( т е, если поезд может доехать из А в Б, то автоматом может и из Б в А - намек на неориентированный граф ).
Каждая железная дорога характеризуется:
1. своей протяженностью ( например, в км. )
2. максимальным весом ( например, в тонн. ) поезда, который может по ней ехать.

Вот один из примеров:

Прикреплённая картинка

Например, железная дорога из Самары в Новгород ( или наоборот - не важно ) имеет протяженность 4 км. и по ней может ехать поезд весом НЕ БОЛЕЕ 7 тонн.
И нужно найти кратчайший путь ( в км. ) между двумя заданными городами.
--------------------------------------------------------------------------------
Я так понимаю, что здесь почти классический алгоритм Dijkstra, но с ограничением на тоннаж поезда. Если убрать тоннаж, то в чистом виде Дейкстра был бы.
Поэтому достаточно просто исключить ВСЕ дороги между городами, у которых допустимый вес поезда строго меньше веса поезда.
Например, берем вес поезда = 5 тонн.
Получается такое что-то:

Прикреплённая картинка

Если совсем удалить дороги, то получается такое:

Прикреплённая картинка

И после этого запускается алгоритм Дейкстры от заданного города и все.
Все верно в этих рассуждениях?) Уверен на 95%, что, да, так и нужно, но мало ли...
--------------------------------------------------------------------------------
И 2ой момент по этому заданию, который плоховато понимаю совсем.
Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.
Это случаем не построение остова, только не минимального, как принято, а максимального? + при этом фактор протяженности вообще не играет никакой роли, как понимаю, нужно смотреть ТОЛЬКО на тоннаж.
Или есть какое-то стандартное название алгоритма для такого задания?
--------------------------------------------------------------------------------
И момент 3ий.
Какой формат описания графа является оптимальным для решения этих подзадач? Скорее всего, здесь либо матрица смежности, точнее весовая матрица + матрица протяженности, либо список смежности. Но вроде с весовыми матрицами поудобнее работать + попроще, что ли. Какой бы формат выбрали вы? Возможно, что для разных подзадач ( #1, #2 ) не один и тот же.

спс. за внимание, буду очень признателен за любую помощь

Сообщение отредактировано: FasterHarder - 28.06.22, 03:03

[Akina]

1. Если поезд неделим, то да - выбрасываем рёбра, не отвечающие условию, применяем Дейкстру.
2. Это будет обычный поиск всех путей в графе между заданными узлами. Просто в процессе построения дополнительно считается и вес, который пропустит путь. Ну а потом тупая сортировка.
3. Я бы выбрал именно матрицу смежности. Просто вместо тупых единичек там будет нагрузочная способность ребра.

[m-ch]

Цитата

Какой формат описания графа является оптимальным для решения этих подзадач?

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

Цитата

Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса

Может подойдет алгоритм Форда-Беллмана, только вместо выбора минимального веса в ребрах выбирать максимальную грузоподъёмность
По сути задача похожа на эту: https://www.cyberforum.ru/algorithms/thread2992509.html

Сообщение отредактировано: m-ch - 28.06.22, 06:09

[FasterHarder]

Цитата Akina @ 28.06.22, 04:29

1. Если поезд неделим, то да - выбрасываем рёбра, не отвечающие условию, применяем Дейкстру.

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

Цитата Akina @ 28.06.22, 04:29

2. Это будет обычный поиск всех путей в графе между заданными узлами. Просто в процессе построения дополнительно считается и вес, который пропустит путь. Ну а потом тупая сортировка.

Так, а вот здесь хочется кое-что понять.
Обычный поиск ВСЕХ путей графа - это ведь полный перебор получается всех возможных путей + их надо где-то сохранить, чтобы потом отсортировать тупой сортировкой).
И поясни, плз, чем вариант с построением максимального остова плох?? Там тоже сначала надо будет отсортировать по убыванию нагрузки дороги и добавлять по одному ребру, начиная, с самого тяжелого. Разве это НЕ проще, чем полный перебор путей? + нет полных переборов, т е время работы алго будет быстрее. Возможно, что я здесь дико туплю и чего-то не выкупаю с этим макс.остовом.
Кстати, этих остовов макс. тоже может быть больше 1го(. Да, наверное, не факт, что это ПРОЩЕ, чем полный перебор всех путей...
*"прочность" искомого маршрута характеризуется самым слабым его звеном - просто так написал)
Если искать все пути, то это ведь рекурсивный BFS/DFS, наверное...

Цитата Akina @ 28.06.22, 04:29

3. Я бы выбрал именно матрицу смежности. Просто вместо тупых единичек там будет нагрузочная способность ребра.

+1, для задачи #1 достаточно иметь матрицу расстояний. Для задачи #2 пока непонятно, поэтому структуры данных нужно будет еще тщательно продумать...


m-ch, привет! Залетай почаще в обсуждения графов - любопытно почитать твои мысли по ним)

Цитата m-ch @ 28.06.22, 05:57

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

ну это так на данный картинке, теоретически граф может быть полным.
кстати, это деление на разреженные/не разреженные графы вроде как условно.
припоминаю, что считают некий коэффициент, как отношение [текущего количества ребер] / [количество ребер полного графа]. Если K = 1 - полный граф, если 0 - пустой, у которого все вершины изолированные.
Чему должен быть равен этот коэффициент ( из интервала ( 0; 1 ) ), чтобы отнести граф к разреженным?) Ты для себя, чему этот коэффициент принимаешь или на "глазок" больше?

Цитата m-ch @ 28.06.22, 05:57

Может подойдет алгоритм Форда-Беллмана

емнип, у него акцент на орграфы + когда есть отр.веса. В этой задаче все числа положительные + неорграф.
Хотя понятно, что и Дейкстру и Форд-Беллман можно применить, но по Дейкстре хоть что-то помню), поэтому выберу Dijkstra

Akina, m-ch, спс за ответы

[Akina]

Цитата FasterHarder @ 28.06.22, 07:04

в каком контексте имеешь ввиду "делимость поезда"?

Применительно к нагрузочной способности ребра. Т.е. поезд в 7 тонн нельзя разделить на два, в 3 и 4 тонны, и пропустить по ребру с нагрузочной способностью не более 5 тонн.

Цитата FasterHarder @ 28.06.22, 07:04

Обычный поиск ВСЕХ путей графа - это ведь полный перебор получается всех возможных путей + их надо где-то сохранить, чтобы потом отсортировать тупой сортировкой

У тебя не поиск всех путей, а поиск всех путей из заданного начала в заданный конец. И тут подойдёт обычный поиск в ширину, например.

Цитата FasterHarder @ 28.06.22, 07:04

для задачи #1 достаточно иметь матрицу расстояний.

А эта задача вообще не оперирует весом состава. А если его учитывать - то получается задача с двумя критериями, для которых ты не задаёшь приоритет. Что лучше - маршрут 100 км на 5 тонн или 150 км, но на 7 тонн? а фиг знает... критерий должен быть один, а не два.

[FasterHarder]

Цитата Akina @ 28.06.22, 08:17

Применительно к нагрузочной способности ребра. Т.е. поезд в 7 тонн нельзя разделить на два, в 3 и 4 тонны, и пропустить по ребру с нагрузочной способностью не более 5 тонн.

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

По заданию #2 вот еще раз формулировка: "нужно найти МАРШРУТ между двумя разными городами, чтобы проехал поезд макс. веса".
Т е нужно найти единственный маршрут. Если их несколько, то любой подойдет, наверное.
А ведь в графе может быть бесконечное число маршрутов, т к в маршруте могут повторяться ребра и вершины. Но здесь это бессмысленно ( петлять поезду нет смысла ), т к пройденное расстояние вообще ни на что не влияет. Поэтому задачу можно свести к поиску пути ( все ребра и все вершины различны ) вроде бы.

Чтобы найти нужный маршрут нужно перебрать их все. То есть от перебора никуда не деться.
Кстати, ответом будет прочность самого слабого звена маршрута/пути - именно поезд такого предельного веса сможет курсировать по этой траектории.
---------------------------------------------
Akina, поясни, плиз, а разве нельзя и в этой подзадаче применить Дейкстру, только перевернутого.
Т е есть матрица прочности ( хранит тоннаж ).
От заданного города находим максимальные "расстояние" до каждой вершины.
Затем восстанавливаем траекторию: от конечного города двигаемся к начальному и одновременно с этим запоминаем минимальный тоннаж ( это и будет ответом ) + можно и сам маршрут вывести.
Разве это не будет работать и это полный бред??)

Просто BFS / DFS больше предназначен для обхода + там какая-то рекурсия неудобная вроде и пр. неприятности ), а перевернутый Дейскстра мне понятен на 99%...

[Akina]

Цитата FasterHarder @ 28.06.22, 11:51

а разве нельзя и в этой подзадаче применить Дейкстру

А кто мешает-то? Только я как-то смысла не вижу. От поиска в ширину он будет отличаться исключительно порядком сканирования вершин.

Цитата FasterHarder @ 28.06.22, 11:51

Затем восстанавливаем траекторию

Зачем? проще её сразу тащить - всё равно вес-то тащим.

[FasterHarder]

Цитата Akina @ 28.06.22, 12:51

А кто мешает-то? Только я как-то смысла не вижу. От поиска в ширину он будет отличаться исключительно порядком сканирования вершин.

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

Прикреплённая картинка

Я так понимаю, что ты с ними категорически не согласен? ))

Цитата Akina @ 28.06.22, 12:51

Зачем? проще её сразу тащить - всё равно вес-то тащим.

попробую подумать над этим моментом

Akina, в целом большое спс. за помощь. Мне нужно подтягивать знания в вариантах, когда нужно что-то перебирать на графах рекурсивно, т к плоховато понимаю, как внедрить в таких случаях эти BFS / DFS...

[Akina]

Цитата FasterHarder @ 28.06.22, 20:41

Я так понимаю, что ты с ними категорически не согласен?

Какой смысл соглашаться или не соглашаться с совсем другим методом?

Всё прекрасно получится. Другой вопрос, что поиск в ширину не выглядит оптимальным при фиксированных начальном и конечном узлах - но он так только выглядит. Ведь и тот, и другой поиски предполагают полный перебор и различаются только в порядке перебора. Как, кстати, и Дейкстра.

Хотя есть и подвох. Что DFS, что BFS - они в основном предназначены для поиска в древовидных и близких к ним графах и имеют определённые проблемы при работе с полными и близкими к ним графами, в случае которых (тут ты был, наверное, прав) надо скорее думать о волновом алгоритме.

[FasterHarder]

Цитата Akina @ 29.06.22, 04:27

Какой смысл соглашаться или не соглашаться с совсем другим методом?

а я вообще ни на грамм не уверен, что у них правильно написано, т к не понимаю до конца)

Цитата Akina @ 29.06.22, 04:27

Что DFS, что BFS - они в основном предназначены для поиска в древовидных и близких к ним графах и имеют определённые проблемы при работе с полными и близкими к ним графами

это золотые слова!

Цитата Akina @ 29.06.22, 04:27

тут ты был, наверное, прав

ну, хоть один раз из 100, хоть в чем-то, наверное, прав
----------------------------------------------------

Касательно построения максимального остова - встретил такое понятие в теории графов - редкая штука. В 1000 раз чаще минимальным остовом орудуют.
Вот граф для подзадачи #2. Весом ребер выступает прочность железной дороги. Здесь вообще не сдалась инфо о протяженности, поэтому отбросим ее сразу, чтоб НЕ мешала и НЕ отвлекала:

Прикреплённая картинка

Максимальным остов получается вроде таким:

Прикреплённая картинка

Как я понимаю, справедливы следующие утверждения:
1. Т к сначала задаются города для проложения маршрута, то выбирать можно ребро ( с макс. прочностью ) инцидентное стартовой вершине
2. Необязательно строить ВЕСЬ макс. остов. Если было добавлено ребро, инцидентное конечной вершине - конец - маршрут проложен + он не может быть улучшен по прочности.
3. Ответом является самое слабое по прочности ребро. Его можно сразу рассчитывать, при добавлении очередного ребра в макс остов.

По сложности работы алго все достаточно плохо. В худшем случае, когда лишь на последней итерации прокладываются ребро до конечной вершины ( n - 1 по счету итерация, где n - количество вершин ), получается что-то около O( n^3 ), т к на каждой итерации надо просмотреть каждую вершину, которая "в работе" + у нее всех соседей. Все это дело помрет, наверное, уже от 500-1000 вершин).

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

Не уверен, что этот макс. остов вот прям всегда работает правильно, т к эти графы бесконечно коварны и в запасе у них море подлянок))

[m-ch]

FasterHarder
Можешь приложить описание реального графа (сети дорог)?
Сколько вершин и сколько ребер ориентировочно?

[FasterHarder]

m-ch
я бы рад, но у меня и в помине нет никакого реального графа.
Количество вершин и ребер - произвольное количество ( в рамках разумного ).

m-ch, у меня по этой задачке все алгоритмически почти готово ( Дейкстра на 100% ), а это макс. дерево на 80%, т к еще не оч.понятно, как восстанавливать путь между заданными вершинами. Над этим потихоньку думаю.

[esperanto]

@Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса.@

Есть задача найти путь когда длина пути это вес максимального ребра в нем, кажется это то, что надо?

[FasterHarder]

Цитата esperanto @ 30.06.22, 17:37

Есть задача найти путь когда длина пути это вес максимального ребра в нем, кажется это то, что надо?

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

зы: кстати, макс. остов обычно строят, просто меняя заданные веса ребер на отрицательные ( то, что было самым большим, становится самым маленьким ) и затем стандартный мин.остов

[m-ch]

Как я вижу решение задачи № 2: "Нужно построить маршрут движения поезда между двумя заданными городами, чтобы по нему могли ездить поезда максимально возможного веса."

1. Строим максимальное оставное дерево (аналогично, как и минимальное), используя пропускную способность ребер.
2. Находим по остову маршрут от заданных точек начала и конца любым алгоритмом (наверно подойдет волновой алгоритм)
3. По найденному маршруту определяем минимальный вес в маршруте, это и будет ограничение поезда из одного города в другой
4. Из исходного графа удаляем все ребра с пропускной способностью менее найденной и далее строим кратчайший маршрут Дейкстрой (или алгоритмом Левита, или Форда-Беллмана)от начальной до конечной точки, при этом вес поезда будет не менее уже определенного, а маршрут будет кратчайший из возможных.

Есть мысль, что п. 1 и 2 можно решить достаточно просто, немного изменив алгоритм Флойда-Уоршелла и за O(n^3) найдем все возможные максимальные веса поездов между всеми вершинами.
Если граф большой - несколько тысяч вершин, что вполне может быть для описание всех железнодорожных станций, то перебор O(n^3) будет сделать затруднительно

[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