WikiSort.ru - Не сортированное

Сохранение кратчайших путей

Лемма (Изменение весов сохраняет кратчайшие пути). Пусть дан взвешенный ориентированный граф ${\displaystyle G=(V,\;E)}$ с весовой функцией ${\displaystyle \omega \colon E\to R}$ , и пусть ${\displaystyle h\colon V\to R}$  — произвольная функция, отображающая вершины на действительные числа. Для каждого ребра ${\displaystyle (u,\;v)\in E}$ определим

${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v).}$

Пусть ${\displaystyle p=\langle v_{0},\;v_{1},\;\ldots ,\;v_{k}\rangle }$  — произвольный путь из вершины ${\displaystyle v_{0}}$ в вершину ${\displaystyle v_{k}}$ . ${\displaystyle p}$ является кратчайшим путём с весовой функцией ${\displaystyle \omega }$ тогда и только тогда, когда он является кратчайшим путём с весовой функцией ${\displaystyle {\hat {\omega }}}$ , то есть равенство ${\displaystyle \omega (p)=\delta (v_{0},\;v_{k})}$ равносильно равенству ${\displaystyle {\hat {\omega }}(p)={\hat {\delta }}(v_{0},\;v_{k})}$ . Кроме того, граф ${\displaystyle G}$ содержит цикл с отрицательным весом с использованием весовой функции ${\displaystyle \omega }$ тогда и только тогда, когда он содержит цикл с отрицательным весом с использованием весовой функции ${\displaystyle {\hat {\omega }}}$ .

Изменение веса

1. Для данного графа создадим новый граф ${\displaystyle G'=(V',\;E')}$ , где ${\displaystyle V'=V\cup \{s\}}$ , для некоторой новой вершины ${\displaystyle s\not \in V}$ , а ${\displaystyle E'=E\cup \{(s,\;v):v\in V\}}$ .
2. Расширим весовую функцию ${\displaystyle \omega }$ таким образом, чтобы для всех вершин ${\displaystyle v\in V}$ выполнялось равенство ${\displaystyle \omega (s,\;v)=0}$ .
3. Далее определим для всех вершин ${\displaystyle v\in V'}$ величину ${\displaystyle h(v)=\delta (s,\;v)}$ и новые веса для всех рёбер ${\displaystyle {\hat {\omega }}(u,\;v)=\omega (u,\;v)+h(u)-h(v)\geqslant 0}$ .

Основная процедура

В алгоритме Джонсона используется алгоритм Беллмана — Форда и алгоритм Дейкстры, реализованные в виде подпрограмм. Рёбра хранятся в виде списков смежных вершин. Алгоритм возвращает обычную матрицу ${\displaystyle D=d_{ij}}$ размером ${\displaystyle |V|\times |V|}$ , где ${\displaystyle d_{ij}=\delta (i,\;j)}$ , или выдает сообщение о том, что входной граф содержит цикл с отрицательным весом.

Алгоритм Джонсона
Строится граф ${\displaystyle G'}$

if Bellman_Ford${\displaystyle (G',\;\omega ,\;s)}$
 = FALSE
   then print «Входной граф содержит цикл с отрицательным весом»
   else for для каждой ${\displaystyle v\in V'}$

        do присвоить величине ${\displaystyle h(v)}$
 значение ${\displaystyle \delta (s,\;v)}$
,
           вычисленное алгоритмом Беллмана — Форда
        for для каждого ребра ${\displaystyle (u,\;v)\in E'}$

            do ${\displaystyle {\hat {\omega }}(u,\;v)\leftarrow \omega (u,\;v)+h(u)-h(v)}$

        for для каждой вершины ${\displaystyle u\in V}$

            do вычисление с помощью алгоритма Дейкстры
            ${\displaystyle (G,\;{\hat {\omega }},\;u)}$
 величин ${\displaystyle {\hat {\delta }}(u,\;v)}$

            для всех вершин ${\displaystyle v\in V}$

            for для каждой вершины ${\displaystyle v\in V}$

                do ${\displaystyle d_{uv}\leftarrow {\hat {\delta }}(u,\;v)+h(v)-h(u)}$

   return D