Теория на графите, тема 2 част 2.

Най-къс път в граф, когато теглата на ребрата са константа

Сега ще разгледаме алгоритъм за тази сравнително по-лесна модификация на задачата за най-къс път. Ще ползваме за тегло на ребрата 1-ца. Алгоритъмът е известен като търсене в широчина (BFS). В масива п ще пазим най-късия път от връх 1 до всеки друг път в графа ( пi = q означава, че най-късия път до i-ия връх е с q на брой ребра).

Инициализация
#п1 = 0;
#пi = inf, $i \ge 2$;
#k = 0, S = {1}, S0 = {1};

Стъпка k:
1. Sk = {i | пi = k}
2. S = {i | пi $\le k$};
3. Sk + 1 = Г(Sk) ⋂ $\overset{-}{S}$;
4. пi = k + 1, $\forall i \in S_{k + 1}$;
5. S = $S \bigcup S_k$;
6. ако |S| = |V| край;
7. k = k + 1, goto 1;

Пояснения: Г() използваме като операция за извличане на наследниците на даден връх или множество от върхове. $\overset{-}{S}$ e отрицание на S.

Сложност: О(М), където М е броят на ребрата. За да достигнем тази сложност, ползваме списък на наследниците.

Най-къс път в произволен граф с произволно тегло на ребрата.

Няма алготиръм, който да търси най-къс път в граф с отрицателни цикли, тъй като това би било безсмислено. Има подходящи подходи за решаване на проблема за най-къс път, чрез които може да се намират такива цикли, или ако няма отрицателни цикли, все пак да оценим най-късите пътища от даден връх до всички останали.

Алгоритъм на Белман-Форд

Алгоритъмът на Белман - Форд се основава на простото неравенство : $d_j \le d_i + l(i,j)$, за всеки i, j - върхове на графа, където di и dj са съответно най-късите пътища от връх 1 до върховете i и j, теглото на реброто (i,j) бележим с l(i,j). Горното неравенство ще запишем като : $d_j - d_i \le l(i,j)$ от съображения за overflow, заради началната инициализация с inf (или максималната стойност за дадения тип данни).

Инициализация
#d1 = 0;
#di = inf, $\forall i \ne 1$;

Стъпки

  1. Търси (i,j) такива че: $d_j - d_i > l(i,j)$;
  2. Ако не съществува дъга (i,j) с горното качество, край;
  3. dj = di + l(i,j), goto 1;

Доказателство че алгоритъмът работи: Достатъчно е да приложите един път алгоритъма(хартия + химикал, моля), за да се ориентирате че на първа стъпка оптимизираме d за непосредствените съседи на началния връх (по традиция връх 1) ползвайки максимум 1 дъга за да стигнем от 1 до всеки друг връх, на втора стъпка оптимизираме за най-близките, техни съседи ползвайки максимум 2 дъги и т.н. Следователно на стъпка k, в d ще пазим най-късите пътища от 1 до всички останали върхове изполващи максимум k дъги. Горните разсъждения ни водят на мисълта, че след максимум N - 1 стъпки, в масива d ще сме намерили глобално най-късите пътища от 1 до всички останали върхове в графа.

Динамична реализация:
Тук в dкi ще пазим най-късия път от връх 1 до връх i ползващ неповече от к ребра, $1 \le i \le N \mbox{ and } 1 \le k \le M$, за граф G(V, A) с N върха и M ребра.
-Инициализация:

  1. d01 = 0;
  2. d0i = inf, $\forall i > 1$;
  3. k = 1;

- Стъпкa k:

  1. dk1 = 0;
  2. $d^k_i = \min ( d^{k - 1}_i, \underset{j : \exists (j,i)}{\min}(d^{k - 1}_j + l(j,i)))$;
  3. aко dki = dk - 1i $\forall i \Rightarrow$ stop;
  4. aко $k \le N - 1$, goto 1;
  5. else - има отрицателни цикли.

Сложност и качества на динамичната реализация: Сложността е О(N3), което най-малкото личи от 3-те променливи i, j, k, които се менят от 1 до N (за k e N - 1). Важно е последното действие от стъпката, ако вече k е надминало N - 1, и все още съществуват двойка върхове i и j, за който е в сила : $d^k_j - d^k_i > l(i,j)$, следва че съществува отрицателен цикъл, в който i и j участват.

Най-къс път в произволен граф без ориентирани цикли.

За този по-специален случай на граф главната идея е: $d_i = \underset{\exists (j,i)}{\min} d_j + l(j,i)$. За да приложим алгоритъма по-ефективно, можем първо да сортираме графа топологически. На самия алгоритъм за намиране на най-къс път няма да се спираме, тъй като той е от 2 for-а (C++ №1 xD), но ще разгледаме една реализация на топологическо сортиране.

Топологическо сортиране Първо да дефинираме това понятие: Граф е топологически сортиран, ако върховете му са наредени в редица, такава че ако има дъга от връх i до връх j, то i предхожда j в редицата.

Алгоритъмът:

Със Si бележим множеството от върховете j, за който на i-тата стъпка имаме dj- = 0. С ri бележим най-дългия път като брой ребра от 1 до връх i.

Инициализация

  1. di- = |Гi-1| $\forall i$;
  2. k = 0;
  3. S0 = {i | di- = 0};

Стъпка k
1. $S_{k+1} = \varnothing$;
2. $\forall i \in S_k$ do:

  • ri = k;
  • $\forall j \in$ Гi :
  • dj- = dj- - 1;
  • if dj- = 0
  • $S_{k+1} = S_{k+1} \bigcup \{ j \}$;

3. k = k + 1;
4. if |Sk| = 0, end;
5. goto 1.

Сложност и резултати: Сложността е (O (|M| + |N|), където М е броят на ребрата в графа, a N - броят на върховете.
За всяко $n \in N$ имаме: $O(1) + O($Г$^{-1}_{n}) = O(|N| + |M|)$.

За да може да намерим н.к.п. от връх 1 до всички останали, просто правим така:
нека k : 1 ∈ Sk
За всяко i : i ∈ Sl && l > k do:

  • за всяко j : j ∈ Sm && k < m < l && (j, i) ∈ E, do:
      • di = min{di , dj + l(j, i)}

Намиране най-късите пътища между всички двойки върхове

Алгоритъм 1 за произволен граф

Дефиниция: Матрица Wk ще наричаме матрица NxN (където N е големината на V), такава че всеки нейн елемент dkij е дължината на най-къс път от i до j с не повече от k дъги.
От дефиницията следва директно за W1,

(1)
\begin{align} d^1_{ij} = \begin{cases} 0 & \mbox{if i = j; } \\ l(i,j) & \mbox{if (i,j) } \in A;\\ \inf & else; \\ \end{cases}\\ \end{align}

За да намерим най-късите пътища между всички двойки върхове, използваме рекурентната формула:
$d^k_{ij} = \min \{ d^{k - 1}_{ij}, \underset{t = 1...n}{\min} \{ d^{k - 1}_{it} + l(t,j) \} \} = \underset{t = 1...n}{\min} \{ d^{k - 1}_{it} + l(t,j) \}$
к върви от 1 до N - 1, тъй като вече знаем, че най-късите пътища в един граф са прости.

Сложността на реализиране на тази формула е О(N4). Има възможност да се оптимизира, като се сведе до умножение на матрици, което горепосочената формула изключително много наподобява. Ето как изглежда умножение на матрици (за тези които са забравили) $c_{ij} = \underset{k = 1}{\overset{n}\sum} a_{ik}b_{kj}$, за нашата формула просто сменяме $\sum$ с $\min$ и умножението със събиране и готово. Със свеждане до умножение на матрици и прилагане на бързо вдигане на степен може да се постигне сложност от O(N3logN).

Ето как ще изглежда намирането на Wk само ползвайки матрици:
W1 . W1 = W2;
W2 . W1 = W3;

WN - 2 . W1 = WN - 1;
Като WN - 1 != WN <=> съществува ориентиран отрицателен цикъл в G.

Алгоритъм 2 за произволен граф - Алгоритъм на Флойд - Уоршал

Алгоритъмът на Флойд - Уоршал е доста популярен и със сигурност най-бързия за писане алгоритъм за намиране на пътищата от всеки връх до всеки друг при граф с произволно тегло на дъгите. Идеята, на която е базиран самият алгоритъм е: разглежда се най-късият път от връх i до връх j с първите k върха като възможни междинни(което ще пазим в Dk(i,j)).

Алгоритъмът:

- с Пk(i,j) ще бележим последния междинен връх по пътя от i до j с първите k върха като възможни за междинни (нещо като двумерен списък на бащите);

Инициализация:

(2)
\begin{align} D^0_{(i,j)} = \begin{cases} l(i , j) & \mbox{if } \exists (i,j) \in A\\ \inf & else\\ \end{cases}\\ \end{align}

За П0 да се има в предвид, че върховете се броят от 1.

(3)
\begin{align} \Pi^0_{(i,j)} = \begin{cases} i & \mbox{if }\exists (i,j) \in A\\ 0 & else\\ \end{cases}\\ \end{align}

Стъпка k, k = 1…N:

$\mbox{for } \forall \mbox{ i from 1 to N}$

  • $\mbox{for } \forall \mbox{ j from 1 to N}$ :
(4)
\begin{align} D^k_{(i,j)} = \min \{ D^{k - 1}_{(i,j)}, D^{k - 1}_{(i,k)} + D^{k - 1}_{(k,j)} \} \\ \end{align}
(5)
\begin{align} \Pi^k_{(i,j)} = \begin{cases} \Pi^{k - 1}_{(k,j)} & \mbox{if } D^{k - 1}_{(i,k)} + D^{k - 1}_{(k,j)} < D^{k - 1}_{(i,j)} } \\ \Pi^{k - 1}_{(i,j)} & \mbox{else }\\ \end{cases}\\ \end{align}

Алгоритъм 3 за произволен граф - Алгоритъм на Джонсън

Идеята на този алгоритъм се крие в 2 отделни етапа на решаване на задачата. Първо премахване на отрицателните тегла на дъгите, след това прилагане на Дейкстра N пъти (да си припомним че алгоритъмът на Дейкстра не работи с графи с дъги с отрицателно тегло). Ще се спрем само на първия етап и то по-обстойно.

Преди самия алгоритъм, да се спрем на техника употребявана в Дискретната Оптимизация. Да разгледаме системата неравенства:
$x_i - x_j \le b_k \forall \mbox{ i, j from 1...N, k = 1...M}$
Да построим граф G(V,A) за системата, като етикети на върховете ще са индексите на променливите xi xj - i, j, а дъга между всеки i, j от V ще съществува, само когато променливите xi и xj участват в неравенство, теглото на дъгата ще е съответното bk. След като сме построили нашия граф G използвайки всички неравенства от системата, построяваме $G` = (V \bigcup \{S\}, A`)$, където S е с дъги до всички останали, теглото на които е 0. Ето прост пример, за как ще изглежда "парче" от целия граф (върха горе в дясно е j, MSPaint sux…):

johnsonzo4.png

Да разгледаме един пример за ориентиран цикъл във формата му като неравенства:
|$x_2 - x_1 \le b_1$
|$x_3 - x_2 \le b_2$
|$x_4 - x_3 \le b_3$
|$x_1 - x_4 \le b_4$

Сумираме левите и десните страни и получаваме, че ако системата има реални решения, то:
$b_1 + b_2 + b_3 + b_4 \ge 0$
По друг начин казано, за да има системата решение, то трябва да няма отрицателно ориентирани цикли в графа G. Така след като видяхме, че разнообразни проблеми са сводими до задача за граф(и обратно), да забравим как сме стигнали до G нека това ни е изходния граф за задачата. Нека в G няма ориентирани отрицателни цикли. Прибавяме S по горепосочения начин и търсим най-късите пътища от S до всички останали върхове, задача с която вече сме се сблъсквали. За целта ще използваме алгоритъма на Белман- Форд.

Ще бележим с $\rho_i$ н.к.п. (най-късият път) от S до връх i. Всъщност, $\rho_i$ се оказва и решението за xi за системата от неравенства, която разглеждахме по-рано.

Алгоритъмът:

  1. ползвайки Белман-Форд, стигаме до $\rho_i , \rho_j$ такива, че $\rho_i + c_{ij} \ge \rho_j \Rightarrow c_{ij} - \rho_j + \rho_i \ge 0$.
  2. означаваме с $c^-_{ij}$ новите тегла на дъгите в нашия граф, като $c^-_{ij} = c_{ij} - \rho_j + \rho_i$
  3. с новите тегла на дъгите: $c^-_{ij}$, които са неотрицателни, прилагаме алгоритъма на Дейкстра N пъти, взимайки всеки връх като начален по веднъж.
  4. преработваме получените н.к.п. за $c^-_{ij}$, така че да са верни за теглата cij.

Следните разсъждения може да се използват като доказателство на твърдението, че горепосоченият алгоритъм си върши работата.
Преработването се осъществява така:
Както знаем:

  1. $c^-_{ij} = c_{ij} - \rho_j + \rho_i$;
  2. н.к.п. в граф са прости пътища

$\Rightarrow$ да разгледаме един път от u до v:
$c^-_{ui_1} + c^-_{i_1i_2} + ... + c^-_{i_nv} = c_{ui_1} + \rho_u - \rho_{i_1} + c_{i_1i_2} + \rho_{i_1} - \rho_{i_2} + ... + c_{i_nv} + \rho_{i_n} - \rho_{v} =$
$\underset{j = i_0}{\overset{i_n}\sum} c_{i_ji_{j + 1}} + \rho_{i_0} - \rho_{i_n + 1}$, където i0 = u и in + 1 = v. С това доказахме, че н.к.п. в графа с тегла $c^-$ се различава от н.к.п. в графа с първоначалните тегла с някаква константа.

Сложност: O(max{N(M+NlogN), NM}) = O(NM) = O(N3), където N = |V| и M = |A|. Сложността е определена от стъпки 1 и 3, съответно сложността на Белман-Форд е О(NM), а на Дейкстра О(M + NlogN).
Ъм… Форд-Белман е на четири реда, а е точно толкова бърз, колкото този. Ако не и по-бърз. Само за сведение. Алгоритъма на Джонсън е добър при редки (sparse) графи - при които M « N.

Примери за задачи за най-къс път в графи.

Задача 1: Дадени са N валути и обменен курс между някои двойки от тях: от валута i до j ще бележим курса с cij . Да се намери стратегия на обмен, която да ни доведе до печалба.

Задача 2: За извършване на даден проект трябва да се изпълнят N работи в определен ред (релация предшества). Могат да бъдат изпълнявани неограничен брой задачи наведнъж, но ако A предшества B, то A трябва да бъде изпълнено преди да се изпълни B. Всяка задача се върши за едно и също време. По даден реда, релацията, между работите, определете най-ранния момент за завършване на проекта.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License