Аксиомы для кратчайших путей

Предположим, у нас есть неориентированный взвешенный граф $G = (V, E, w)$ (с неотрицательными весами). Предположим, что все кратчайшие пути в $G$ единственны. Предположим, у нас есть эти пути (последовательности невзвешенных ребер), но мы не знаем саму G. Можем ли мы создать G , который дал бы эти пути как самые короткие за полиномиальное время? Более слабая версия: можем ли мы решить за полиномиальное время, существует ли такая G ?$\binom{n}{2}$$G$$G$$G$

Очевидным необходимым условием является следующее: для каждой пары путей их пересечение также является путем. Достаточно ли этого условия?

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

Можем ли мы создать G, который дал бы эти пути как самые короткие за полиномиальное время? Более слабая версия: можем ли мы решить за полиномиальное время, существует ли такая G?

Ответ - да обоим. Алгоритм Мухаммеда определенно работает, но есть более быстрый и более прямой метод, который устраняет необходимость запуска кубических разделительных оракулов. Пусть вспомогательный неориентированный взвешенный граф, где вес каждого ребра является целым числом, указывающим, сколько из пути, взятых на входе, содержат это ребро. Теперь рассмотрим экземпляр мультикомодового потока с граничной емкостью над (интерпретируя граничные веса как емкости), в котором цель состоит в том, чтобы одновременно протолкнуть 1 единицу потока между каждой парой узлов. Очевидно, что этот экземпляр потока MC может быть удовлетворен путем проталкивания потока естественным образом вдоль путей, указанных на входе. Оказывается, можно доказать, что нашe ∈ E ($H = (V, E, w')$$e \in E$ H ($n \choose 2$$H$ G$n \choose 2$пути являются уникальными кратчайшими путями в некотором тогда и только тогда, когда это единственный способ удовлетворить экземпляр потока MC. Мы можем проверить уникальность, установив LP, чьи ограничения являются обычными для технико-экономического обоснования потока MC, плюс определенную тщательно выбранную целевую функцию, и веса ребер удовлетворяющего могут быть извлечены из двойственного этого LP.$G$$G$

Очевидным необходимым условием является следующее: для каждой пары путей их пересечение также является путем. Достаточно ли этого условия?

Это условие иногда называют «согласованностью» (набор путей непротиворечив, если пересечение любых двух является подпутем каждого). Из вышесказанного следует, что согласованности недостаточно. Один из двух контрпримеров для наименьшего числа является следующей системой с четырьмя путями с цветовой кодировкой на шести узлах:

Другими словами, нет способа присвоить веса 8 ребрам, изображенным здесь, чтобы все эти четыре пути были одновременно уникальным кратчайшим путем между их конечными точками. Тем не менее, любая пара из них пересекается только на одном узле, поэтому они согласованы (даже если мы правильно заполним их несколькими дополнительными путями, чтобы всего). Существует бесконечно много контрпримеров, подобных этому; см. статью для характеристики.$n \choose 2$

Три других быстрых комментария обо всем этом:

1. Аналогичные утверждения, на которые вы могли бы надеяться, справедливы в настройке ориентированных, а не ненаправленных графов,
2. Существует хорошая топологическая интерпретация этой теории, которая приводит к некоторому дополнительному пониманию и интуиции о том, как уникальные кратчайшие пути могут быть структурированы, и
3. По некоторым техническим причинам теория упрощает удобство настройки DAG, а не ненаправленных или (циклических) ориентированных графов.

Вы можете написать проблему как LP, не так ли? Для любых двух вершин u, v и любого пути P от u до v вес P больше или равен весу данного кратчайшего пути между u и v. Это все линейные неравенства, и хотя существуют экспоненциально много, проблема разделения находится в P (это просто проблема кратчайшего пути из всех пар). Таким образом, вы можете использовать алгоритм эллипсоида для его решения.