Вопрос по теории графов, Java.Какой алгоритм позволяет достичь следующего

Question

У меня есть график с X узлами и Y ребрами.Утяжеленные края.Смысл в том, чтобы начать с одного узла и остановиться на другом.И вот тут возникает проблема;

Визуализируйте проблему.Кромки - это дороги, а веса кромок - это максимальные ограничения веса для транспортных средств, движущихся по дорогам.Мы хотели бы проехать на самом большом грузовике из пункта А в пункт Б.Таким образом, максимально допустимый вес для грузовика, движущегося по заданному пути, равен наименьшему весу всех ребер на этом пути.Мне нужен наибольший максимально допустимый вес для всех путей от A до B.

Могу ли я использовать какой-то алгоритм Дейкстры для решения этой задачи?Я не уверен, как выразить эту проблему в виде алгоритма, который я могу реализовать.Любая помощь очень ценится.

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

Answer 1

Алгоритм Дейкстры должен работать, но ваше "расстояние" в данном случае немного странное.Ваше "расстояние" - это грузовик максимального размера, который вы можете проехать до узла.Давайте назовем это M[v] для узла v.Вам нужно обработать узлы в порядке от наибольшего M [v] до наименьшего M [v] (противоположно нормальному Дейкстре) и вычислить для каждого ребра e от v до w:

M[w] = max(M[w], min(e.weight, M[v]))

Answer 2

Это звучит (почти) точно так же, как проблема с максимальным расходом которые могут быть эффективно решены с помощью Алгоритм Форда-Фулкерсона.

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

Answer 3

Я думаю, вы ищете это

Кратчайший путь

Редактировать:на самом деле вас нет, и ссылка на максимальный поток верна

Answer 4

Итак, если я правильно понимаю, вы спрашиваете: "Какой самый большой грузовик может проехать из пункта А в пункт Б"?

Чтобы применить алгоритм Дейкстры, вам понадобится способ моделирования "стоимости".Если вы хотите использовать стандартную реализацию, вы могли бы присвоить стоимости значение, обратное весу.Таким образом, преимущество с наибольшей стоимостью - это преимущество с наименьшим максимальным весом.Конечно, поскольку вы, вероятно, хотите использовать хорошие целые числа, вы можете просто изменить сравнения вместо фактического использования обратных значений.

Answer 5

Вы хотите оптимизировать [http://en.wikipedia.org/wiki/Flow_network ].Пропускная способность - это максимальный предел веса дороги;а расход - это вес грузовика.

Answer 6

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

Answer 7

Это не проблема ни кратчайшего пути, ни максимального расхода.На самом деле никакой проблемы нет.Он заявил - нужен максимальный вес для всех путей от A до B.Так что сгенерируйте все пути из A с помощью BFS.Для всех путей, заканчивающихся на B, найдите минимальный вес ребер пути.

Answer 8

Использование Алгоритм Дейкстры с обратным значением максимального веса грузовика в качестве граничной стоимости и максимального веса отдельных граничных грузов в качестве общей стоимости маршрута.

т. е. edge_cost равен 1/(максимальный вес тележки допускается) в total_cost данного маршрута - это максимум индивидуального edge_costэто одно из всех ребер маршрута.

Answer 9

Различные ответы выше предлагают просто алгоритм Дейкстры с модифицированной весовой функцией.Например, w(e) = -c(e), или 'w(e) = 1/c(e)', где w(e) является весом ребра, используемого алгоритмом, и c(e) - пропускная способность ребра в исходной постановке задачи.

Это не работает.

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

a---3-->b---3--->c---3-->d
 \                       ^
  \                      |
   \----------3----------|

Предположим, что значение a ('расстояние до узла a в формулировке алгоритма) равно нулю.Два пути от a Для d эквивалентны в этой задаче.Тем не менее, если мы просто отрицаем пропускную способность границы, расстояние (d), используя длинный путь, равно (-3)+(-3)+(-3) = -9 при использовании короткого пути это было бы -3.Если мы инвертируем пропускную способность ребра, расстояние (d) при использовании длинного пути будет равно (1/3)+(1/3)+(1/3)=1, в то время как это было бы просто (1/3) используя короткий вариант.

Что будет работа заключается в модификации шага релаксации алгоритма, т.е.вместо использования функций сложения (+) и менее чем (<), используя соответствующие функции min и более чем (>), и используйте максимальную кучу вместо минимальной.Мы могли бы избежать последних двух модификаций, если бы отменили веса ребер и использовали значение меньше, чем, но мы никак не можем избежать замены +, поскольку нам нужен какой - то оператор @ где a @ a = a для всех a ценности, тогда как + работает только для a=0.

Итак, единственный правильный ответ, который я вижу, - это самый первый, данный Китом Рэндаллом.

Хорошим упражнением было бы формально доказать, что модифицированный алгоритм верен.Что нужно доказать, так это:- если u является ли узел с максимальным значением d(u) на любой итерации цикла ни один путь, включающий немаркированные узлы, не может создать путь к u получить расстояние, большее, чем d(u).

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