Найти кратчайшие пути в взвешенном унипатическом графе

Направленный граф называется унипатическим, если для любых двух вершин и в графе существует не более одного простого пути из в .$u$$v$$G=(V,E)$$u$$v$

Предположим, мне дан унипатический граф такой, что каждое ребро имеет положительный или отрицательный вес, но не содержит циклов отрицательного веса.$G$

Отсюда я хочу найти алгоритм , который находит все кратчайшие пути ко всем узлам из исходного узла .$O(|V|)$$s$

Я не уверен, как бы я подошел к решению этой проблемы. Я пытаюсь понять, как я мог бы использовать тот факт, что он не содержит отрицательных циклов веса и, конечно, не более одного простого пути между любыми узлами от до .$u$$v$

Выберите представление данных

Сначала посмотрите на размер результата. Вы хотите собрать кратчайшие пути от до каждого другого узла. Если только средняя длина пути не ограничена константой (а это не так: любой список является unipath, и если вы берете корень для общая длина путей равна где равно длина списка), вам нужно быть осторожным в представлении данных: структура, содержащая пути, должна будет использовать совместное использование путей.s n ( n - 1 ) / 2 $s$$s$$n(n-1)/2$$n$

За исключением циклов, существует один путь от до любого другого узла . Если этот путь проходит через промежуточный узел , то первый сегмент пути - это требуемый путь от до . U T S $s$$u$$t$$s$$t$

Я предлагаю сохранить результат в массиве, индексированном узлами, пронумерованными от до , с . Каждый элемент в массиве хранит индекс предыдущего узла на пути к этому узлу (например, используйте в качестве специального маркера для узлов, которые недоступны из ). Путь от до будет .| E | - 1 s = 0 - 1 s s t ( s = R [ … R [ t ] … ] , … , R [ R [ t ] ] , R [ t ] , t $0$$|E|-1$$s=0$$-1$$s$$s$$t$$(s=R[\ldots R[t]\ldots],\ldots,R[R[t]],R[t],t)$

Пройдите по графику

Инициализируйте для всех .- $R$$-1$

Выполните обход графика в глубину или в ширину, начиная с . Каждый раз, когда достигается узел , задайте его предшественник.u R [ u $s$$u$$R[u]$

Поскольку есть циклы, узел может быть достигнут более одного раза. Наличие означает, что уже был посещен.$R[u] \ne -1$$u$

Докажи правильность

Из-за unipathic свойства не имеет значения, как мы достигаем каждого узла, пока мы не завершили цикл. Есть только один простой путь.

Докажите сложность

Алгоритм может достигать каждого узла более одного раза, поэтому не ясно, что его сложность равна . На самом деле проделанная работа где - ребра, которые достижимы из источника. Точнее, мы достигаем узла более одного раза только в одном случае: если узел является первым, которого мы достигаем в определенном цикле, и в этом случае мы достигаем его дважды (один раз с простого пути и один раз после завершения цикла ).Θ ( | E 0 | ) V $O(|V|)$$\Theta(|E_0|)$$V_0$

Ну тогда. Докажем, что в унипатическом графе число элементарных циклов растет максимально линейно с числом узлов. (Элементарный цикл - это цикл, который не содержит более короткий цикл.) В следующем обсуждении я предполагаю, что у графа нет собственного ребра (нет ребра от узла к себе; такие ребра в любом случае не имеют значения для построения пути). ).

Унипатические графы могут иметь циклы, но очень ограниченным образом. Было бы неплохо, если бы мы могли как-то связать каждый цикл с отдельным узлом (или, по крайней мере, с максимальным ограниченным числом циклов на узел). Могут ли циклы делить узел? К сожалению, да.

Вы можете иметь циклов, все совместно использующих один узел и никаких других узлов. Результирующий граф унипатичен. С циклами длины 2 это шаблон звезды с центральным узлом и любым числом узлов таких что .a a b i ∀ i , a ⇆ b $m$$a$$a$$b_i$$\forall i, a \leftrightarrows b_i$

Так что нам нужно больше работать. Что ж, давайте попробуем доказать это индуктивно. Пусть - число узлов в графе , - число ребер, а - количество элементарных циклов, которые не являются само ребрами. Я утверждаю, что если унипатичен и не пуст, то .G # E ( G ) # C ( G ) G # C ( G ) ≤ # V ( G ) - $\#V(G)$$G$$\#E(G)$$\#C(G)$$G$$\#C(G) \le \#V(G)-1$

Для графа с одним или двумя узлами это очевидно. Предположим, что утверждение верно для всех графов, таких что и пусть - унипатический граф с узлами. Если не имеет цикла, , дело закрыто. В противном случае, пусть будет элементарный цикл.G n G 0 = # C ( G ) < # V ( G ) ( a 1 , … , a m$\#V(G) < n$$G$$n$$G$$0 = \#C(G) < \#V(G)$$(a_1,\ldots,a_m)$

Сверните цикл: пусть будет графом, узлы которого являются узлами минус плюс узел а ребра которого являются всеми ребрами не включая , плюс всякий раз, когда и всякий раз, когда . Каждый путь в индуцирует путь в (если путь включает в себя , то замените его на$G'$$G$$\{a_1,\ldots,a_m\}$$a$$G$$a_i$$a \rightarrow_{G'} b$$\exists i, a_i \rightarrow_G b$$b \rightarrow_{G'} a$$\exists i, b \rightarrow_G a_i$$G'$$G$$b \rightarrow a \rightarrow c$$b \rightarrow a_i \rightarrow a_{i+1} \rightarrow \ldots \rightarrow a_j \rightarrow c$ в ). Следовательно, унипатичен. Кроме того, поскольку циклы в не имеют общих ребер, в есть все циклы в кроме исключенного нами: . По индукции . Поскольку , имеем .$G$$G'$$G$$G'$$G$$\#C(G') = \#C(G)-1$$\#C(G') \le \#V(G')-1$$\#V(G') = \#V(G) - m + 1$$\#C(G) = \#C(G')+1 \le \#V(G) - m = n-m \le n-1$

Это завершает доказательство. Обход следует не более ребер.$2|V|-2$