L2.14 Kapitola K2 — Nejkratší cesty (Slot 2) · [NICE] (při časové tísni odložitelná)

Floyd-Warshall (all-pairs) + nejdelší cesty

Jedna nová věc Místo vektoru vzdáleností z jednoho zdroje celá matice vzdáleností mezi všemi dvojicemi vrcholů najednou: Floydův algoritmus iteruje přes mezilehlý vrchol $k$ — $l^k_{ij} = \min\{l^{k-1}_{ij},\ l^{k-1}_{ik} + l^{k-1}_{kj}\}$, celkem $\mathcal{O}(n^3)$.

Všechny dosavadní algoritmy — Dijkstra [L2.4], Bellman-Ford [L2.12], průchod DAGem [L2.13] — řeší variantu single-source: vektor $l(\cdot)$ vzdáleností z jednoho zdroje $s$. Už v [L2.1] ale padla i varianta all-pairs (mezi všemi dvojicemi) — tu potřebuješ např. pro lokační úlohy („kam postavit hasičskou stanici?“, slide 47) nebo pro hledání nejkratšího cyklu v grafu.

Zkus sám: jak spočítat vzdálenosti mezi všemi dvojicemi tím, co už umíš? S jakou složitostí?

Pusť single-source algoritmus z každého vrcholu: $n\times$ Dijkstra dá $\mathcal{O}(n \cdot n^2) = \mathcal{O}(n^3)$ — ale jen pro $c \ge 0$ [L2.4]. Se zápornými hranami $n\times$ Bellman-Ford: $\mathcal{O}(n \cdot nm)$, pro husté grafy ($m \approx n^2$) až $\mathcal{O}(n^4)$.

Floyd zvládne totéž v $\mathcal{O}(n^3)$ i se zápornými hranami (bez záporných cyklů [L2.1]) — a s pseudokódem o třech řádcích smyček.

Nápad: povolené mezilehlé vrcholy

Zkus sám: Bellman-Ford „rostl“ přes počet hran cesty (intuice $k$-tého průchodu [L2.12]). Přes jaký jiný parametr by mohla růst dynamika pro všechny dvojice?

Očísluj vrcholy $1, \ldots, n$ a omezuj, kudy smí cesta vést: $l^k_{ij}$ = délka nejkratší cesty $i \to j$, která smí jako mezilehlé (vnitřní) vrcholy použít jen vrcholy z množiny $\{1, \ldots, k\}$. Pro $k=0$ nejsou povoleny žádné mezilehlé vrcholy — zbývají přímé hrany, takže $l^0$ = matice vah. Pro $k=n$ je povoleno všechno — $l^n$ je hledaná matice vzdáleností.

A přechod $k-1 \to k$? Nejkratší cesta s povolenými $\{1,\ldots,k\}$ buď vrchol $k$ nepoužije (pak je to rovnou $l^{k-1}_{ij}$), nebo ho použije právě jednou — a rozpadne se na úsek $i \to k$ a úsek $k \to j$, oba jen přes $\{1,\ldots,k-1\}$.

Floyd Algorithm — slide 44, 1:1
Zkus sám: proč smíme předpokládat, že cesta použije vrchol $k$ nejvýš jednou? A nerozbije se rekurence tím, že matici přepisujeme „na místě“?

Nejvýš jednou: kdyby sled prošel vrcholem $k$ dvakrát, obsahuje mezi oběma návštěvami cyklus přes $k$. Bez záporných cyklů má ten cyklus délku $\ge 0$, takže jeho vystřižení sled nezhorší [L2.1] — minimum se vždy realizuje i bez opakování.

Přepis na místě: pseudokód níže nedrží dvě matice, přepisuje jedinou. To je v pořádku, protože položky, které iterace $k$ čte ($l_{ik}$ a $l_{kj}$), se v ní samy nemění: $l_{ik} \le l_{ik} + l_{kk} = l_{ik} + 0$ (a stejně pro $l_{kj}$) — řádek a sloupec $k$ jsou v iteraci $k$ stabilní.

Algoritmus

Floyd Algorithm [1962] (Warshall [1962]) — slide 43, 1:1

Input: a digraph $G$ free of negative cycles and weights $c : E(G) \to \mathbb{R}$.
Output: matrices $l$ and $p$, where $l_{ij}$ is the length of the shortest path from $i$ to $j$, $p_{ij}$ is the last but one node on such a path (if it exists).

l_ij := c((i, j)) for all (i, j) ∈ E(G);
l_ij := ∞ for all (i, j) ∉ E(G) where i ≠ j;
l_ii := 0 for all i;
p_ij := i for all (i, j);
for k := 1 to n do                  // for all k check if l_ij improves
    for i := 1 to n do
        for j := 1 to n do
            if l_ij > l_ik + l_kj then
                l_ij := l_ik + l_kj; p_ij := p_kj;
            end
        end
    end
end

Vnitřní if je stará známá relaxace [L2.3] — jen místo hrany $(v,w)$ relaxujeme „zkratku přes $k$“ a místo jednoho vektoru $l(\cdot)$ opravujeme celou matici. Floyd je label-correcting [L2.4]: všechny položky jsou dočasné až do konce běhu.

Zkus sám: proč se při zlepšení nastavuje $p_{ij} := p_{kj}$, a ne třeba $p_{ij} := k$?

$p_{ij}$ má být předposlední vrchol cesty $i \to j$ (výstupní specifikace). Nová cesta je $i \rightsquigarrow k \rightsquigarrow j$ — končí stejně jako úsek $k \rightsquigarrow j$, a jeho předposlední vrchol známe: $p_{kj}$. Vrchol $k$ je jen někde uvnitř, předposlední být nemusí. (Inicializace $p_{ij} := i$ sedí: přímá hrana $(i,j)$ má předposlední vrchol $i$.) Cestu pak rekonstruuješ couváním v řádku $i$ matice: čteš $p_{ij}$, pak $p_{i,p_{ij}}$, … (mění se jen druhý index/sloupec), až dojdeš do $i$ — stejné couvání jako u vektoru $p(\cdot)$ [L2.3].

Běh krok za krokem

Malý digraf se zápornou hranou a cykly (Dijkstra by se spálil, DAG-průchod nelze spustit — graf má cykly). Sleduj, jak se s rostoucím $k$ „otevírají“ nové zkratky:

Zkus sám: proč se sloupec 1 (cesty do vrcholu 1) zlepšil až v poslední iteraci $k=4$?

Do vrcholu 1 vede jediná hrana — $(4,1)$. Každá cesta do 1 tedy končí přes mezilehlý vrchol 4, a ten se „povolil“ až v iteraci $k=4$. Pořadí číslování vrcholů ovlivňuje kdy se která hodnota objeví, ne výsledek — $l^n$ vyjde stejně pro libovolné očíslování.

Složitost, záporné cykly a minimální cyklus

Floyd Algorithm — Complexity and Properties — slide 45, 1:1

The best known algorithm for All Pairs Shortest Path problem without negative cycles.

Johnson's Algorithm is better suited for the sparse graphs — uses Dijkstra and Bellman-Ford, complexity $\mathcal{O}(|V| \cdot |E| \cdot \log |V|)$ (in the simplest case).

Zkus sám: proč $l_{ii} < 0$ právě tehdy, když graf má záporný cyklus?

($\Leftarrow$) Záporný cyklus prochází nějakým vrcholem $i$ a jeho mezilehlé vrcholy jsou nějaká podmnožina $\{1,\ldots,n\}$ — po poslední iteraci je tedy $l_{ii} \le$ délka cyklu $< 0$ (start na diagonále byl $0$ a relaxace hodnoty jen snižují).

($\Rightarrow$) Hodnota $l_{ii} < 0$ vznikla skládáním hran — popisuje uzavřený sled z $i$ do $i$ se zápornou délkou, a ten musí obsahovat záporný cyklus [L2.1]. Stejný „lakmusový papírek“ jako $n$-tý průchod Bellman-Forda [L2.12], tady zadarmo na diagonále. Pozor ale: když $l_{ii} < 0$ nastane, žádná z hodnot $l$ už nejsou vzdálenosti — se záporným cyklem nejkratší cesty nejsou definované.

Trik s diagonálou $l^0_{ii} := \infty$ stojí za zapamatování — přesně tohle chtěla písemka („z výsledku vyčíst minimální cyklus“, viz úloha T02). Diagonála pak místo nul obsahuje délky nejkratších cyklů přes jednotlivé vrcholy. Příklad ze slidu 46 (s touto modifikací):

Matice ze slidu 46, 1:1 — vlevo inicializace ($\infty$ i na diagonále!), uprostřed výsledné $l$, vpravo $p$:

$$ l^0 = \begin{pmatrix} \infty & 3 & \infty & \infty & 4 \\ \infty & \infty & \infty & 2 & 2 \\ \infty & -5 & \infty & \infty & \infty \\ \infty & \infty & 4 & \infty & \infty \\ 6 & -2 & 6 & 0 & \infty \end{pmatrix} \qquad l = \begin{pmatrix} 10 & 2 & 8 & 4 & 4 \\ 8 & 0 & 6 & 2 & 2 \\ 3 & -5 & 1 & -3 & -3 \\ 7 & -1 & 4 & 1 & 1 \\ 6 & -2 & 4 & 0 & 0 \end{pmatrix} \qquad p = \begin{pmatrix} 5 & 5 & 4 & 5 & 1 \\ 5 & 5 & 4 & 2 & 2 \\ 5 & 3 & 4 & 2 & 2 \\ 5 & 3 & 4 & 2 & 2 \\ 5 & 5 & 4 & 5 & 2 \end{pmatrix} $$
Zkus sám: přečti z diagonály $l$ nejkratší cyklus v grafu. Přes který vrchol vede a kudy?

Diagonála je $(10, 0, 1, 1, 0)$ — minimum $0$ u vrcholů 2 a 5: nejkratší cyklus má délku $0$ a je to $2 \to 5 \to 2$ ($2 + (-2) = 0$). Rekonstrukce přes $p$: $p_{22} = 5$ → cyklus končí hranou $(5,2)$; $p_{25} = 2$ → úsek $2 \to 5$ je přímá hrana. Hodnoty $1$ u vrcholů 3 a 4 patří cyklu $4 \to 3 \to 2 \to 4$ ($4 - 5 + 2 = 1$), hodnota $10$ u vrcholu 1 cyklu $1 \to 5 \to 1$. A protipóly: kdyby na diagonále vyšlo záporné číslo, máš v grafu záporný cyklus.

(Volně dle studentské poznámky z testu 2014: hlavní je dát v té úvodní matici pro Floyda na diagonálu nekonečna místo nul, pak člověk rovnou vyřeší i otázku b — přesně tenhle trik.)

K čemu se celá matice hodí, ukazuje hned další slide (47, Location of Fire Station): stanici postav do vrcholu $i$ minimalizujícího $\max_j l_{ij}$ — bez all-pairs matice se minimax lokační úloha řeší těžko. A poznámka ke zkoušce: na rozdíl od Dijkstry a Bellman-Forda (důkazy v kapitole K3) se korektnost Floyda na slidech plně nedokazuje — uč se hlavně běh (matice po iteracích), ne důkaz.

Nejdelší cesty: vynásob váhy −1

Zkus sám: písemka chce nejdelší cesty mezi všemi dvojicemi. Jak na to s Floydem — a kdy to smíš udělat?

Stejný trik jako u DAGu [L2.13]: vynásob všechny váhy $-1$, pusť Floyda beze změny a výsledek vynásob $-1$ zpátky ($q_{ij} = -l_{ij}$). Maximum v $c$ je minimum v $-c$.

Smíš to, jen když negovaný graf splní vstupní podmínku Floyda („free of negative cycles“) — tedy když původní graf nemá kladný cyklus. Kolem kladného cyklu by se dala délka „nabalovat“ donekonečna a nejdelší cesta (bez opakování vrcholů) se stává NP-těžkým problémem (NP-těžké = výpočetně těžké, podrobně v lekci [L2.17]). Záporné cykly v původním grafu naopak nevadí — po negaci jsou kladné.

Ze studentského souhrnu (přepis): „Varianta pre najdlhšiu cestu = ceny hrán vynásobíš $-1$ a klasicky pokračuješ.“

Pozor: tři polopravdy kolem Floyda
Key takeaways — L2.14
T01 Longest paths (all-to-all, Floyd) zdroj: teoreticky_test_final.md strana 3 (EN 1:1 vč. grafu); týž typ úlohy hlásí banka #13 a přepisy testů 2011/12, 2013/14 („graf o 4 uzlech… výsledek byly 4 matice“); řešení vlastní (zdroj řešení nemá)
Assignment (original, EN)

Using Floyd's algorithm calculate square matrix $q$, where $q_{ij}$ is the length of the longest path from vertex $i$ to vertex $j$ (you do not need to calculate matrix of predecessors $p$). Indicate the steps of the algorithm (values of matrix $l$ for 4 iterations of the main loop).

a) Co je v zadání?

Digraf o 4 vrcholech (i se zápornými hranami) a chce se matice nejdelších cest mezi všemi dvojicemi. Odevzdat se mají mezivýsledky: matice $l$ po každé ze 4 iterací hlavní smyčky (matici $p$ zadání výslovně odpouští).

b) Co k tomu budeme potřebovat?

c) Jak nad úlohou uvažovat?

Nejdřív legálnost: najdi všechny cykly grafu a ověř, že žádný není kladný (jinak ×$(-1)$ vyrobí záporné cykly a Floyd nesmí běžet). Pak otoč znaménka vah, sestav $l^0$ (diagonála $0$ — zadání chce délky cest, ne cyklů) a poctivě veď 4 iterace: v iteraci $k$ zkoušej pro každou dvojici $(i,j)$ zkratku $l_{ik} + l_{kj}$. Prakticky: nekonečna se kombinují na nekonečno, takže stačí projít konečné položky sloupce $k$ a řádku $k$. Nakonec $q = -l^4$ — a rozmysli si, co znamená $\infty$ v $l$ pro $q$.

d) Úplné řešení (vlastní)

Kontrola cyklů. Jediný cyklus grafu je $T_1 \to T_2 \to T_1$ s délkou $2 + (-4) = -2 < 0$ — kladný cyklus neexistuje, trik ×$(-1)$ je legální (po negaci má cyklus délku $+2 \ge 0$).

Negace vah a inicializace. Hrany negovaného grafu: $(T_1,T_2) = -2$, $(T_2,T_1) = 4$, $(T_2,T_3) = -1$, $(T_3,T_4) = 1$, $(T_1,T_4) = -2$. Diagonála $0$, jinde $\infty$:

$$ l^0 = \begin{pmatrix} 0 & -2 & \infty & -2 \\ 4 & 0 & -1 & \infty \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \end{pmatrix} $$

Iterace (v každé jen konečné kombinace $l_{ik} + l_{kj}$; zlepšení tučně):

$k=1$: jediná konečná položka sloupce 1 mimo diagonálu je $l_{21} = 4$; zkratky $2 \to 1 \to j$: $l_{24} = \min\{\infty,\ 4 + (-2)\} = \mathbf{2}$ (a $l_{22}$: $4 - 2 = 2 \not< 0$).

$$ l^1 = \begin{pmatrix} 0 & -2 & \infty & -2 \\ 4 & 0 & -1 & \mathbf{2} \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \end{pmatrix} $$

$k=2$: zkratky přes $T_2$ z řádku 1: $l_{13} = \min\{\infty,\ -2 + (-1)\} = \mathbf{-3}$; dále $l_{11}$: $-2 + 4 = 2 \not< 0$, $l_{14}$: $-2 + 2 = 0 \not< -2$.

$$ l^2 = \begin{pmatrix} 0 & -2 & \mathbf{-3} & -2 \\ 4 & 0 & -1 & 2 \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \end{pmatrix} $$

$k=3$: zkratky přes $T_3$ (sloupec 3: $-3, -1$; řádek 3: $l_{34} = 1$): $l_{24} = \min\{2,\ -1 + 1\} = \mathbf{0}$; $l_{14}$: $-3 + 1 = -2$ — remíza s dosavadní hodnotou, ostrý test ($>$) nic nemění.

$$ l^3 = \begin{pmatrix} 0 & -2 & -3 & -2 \\ 4 & 0 & -1 & \mathbf{0} \\ \infty & \infty & 0 & 1 \\ \infty & \infty & \infty & 0 \end{pmatrix} $$

$k=4$: z $T_4$ nevede žádná hrana → celý řádek 4 je $\infty$ (mimo diagonálu) a žádná zkratka $l_{i4} + l_{4j}$ není konečná: $l^4 = l^3$.

Zpětná negace $q_{ij} = -l^4_{ij}$ (pro $l = \infty$ cesta $i \to j$ neexistuje — značíme „—“, nikoliv $-\infty$ jako délku):

$$ q = \begin{pmatrix} 0 & 2 & 3 & 2 \\ -4 & 0 & 1 & 0 \\ \text{—} & \text{—} & 0 & -1 \\ \text{—} & \text{—} & \text{—} & 0 \end{pmatrix} $$

Kontrola vyčerpáním cest: $q_{14}$: přímo $2$, nebo $T_1 \to T_2 \to T_3 \to T_4 = 2 + 1 - 1 = 2$ — shodně $2$ ✓; $q_{24}$: $T_2 \to T_3 \to T_4 = 0$ vs. $T_2 \to T_1 \to T_4 = -2$ → $0$ ✓; $q_{13} = 2 + 1 = 3$ ✓. Diagonála $q_{ii} = 0$ = prázdná cesta (kdyby tě zajímal nejdelší cyklus, použiješ variantu $l^0_{ii} := \infty$ na negovaném grafu — vyšlo by $q_{11} = q_{22} = -2$, cyklus $T_1 \to T_2 \to T_1$).

Krokovaný běh řešení T01 (pozor, spoiler — nejdřív si veď matice sám na papír):

T02 Floyd — minimální cyklus z diagonály zdroj: zkouška 31. 5. 2011 („Floyd, nalézt nenulový minimální cyklus“ — dochován jen CZ titulek, obrázek ne) + přepisy testů 2011/12, 2013/14 („z toho jsme měli vyčíst minimální kružnici“); EN znění rekonstrukce vlastní, instance = příklad ze slidu 46 (matice 1:1 ze slidu), řešení vlastní
Assignment (EN — vlastní rekonstrukce, originál se nedochoval)

Consider the digraph from slide 46 (drawn above in this lesson). Run Floyd's algorithm with the modified initialization $l^0_{ii} := \infty$. (a) Give the initialization of matrices $l$ and $p$. (b) From the resulting matrices read the minimum weight cycle and the minimum nonzero weight cycle; reconstruct the cycles using matrix $p$.

a) Co je v zadání?

Běh Floyda ve variantě „hledám cyklus“: na diagonále inicializace nejsou nuly, ale $\infty$. Z výsledné diagonály se má vyčíst nejlevnější cyklus (a nejlevnější s nenulovou váhou — formulace „nenulový“ z dochovaného titulku připouští obě čtení, vyřešíme obě) a přes matici $p$ ho zrekonstruovat.

b) Co k tomu budeme potřebovat?

  • Tato lekce — varianta $l^0_{ii} := \infty$ (slide 45), čtení matice $p$ couváním po sloupcích.
  • [L2.1] — co by znamenalo záporné číslo na diagonále.

c) Jak nad úlohou uvažovat?

S $l^0_{ii} = \infty$ se diagonální položka může zaplnit jen „oklikou“ $i \rightsquigarrow k \rightsquigarrow i$ — tedy skutečným cyklem; $l_{ii}$ je po doběhu délka nejkratšího cyklu přes vrchol $i$. Minimální cyklus grafu = minimum diagonály. Rekonstrukce: $p_{ii}$ dá poslední hranu cyklu, pak couvej v řádku $i$: $p_{i,p_{ii}}$ atd., dokud se nevrátíš do $i$. Pamatuj, že $l^n_{ii}$ teď není vzdálenost (slide 45).

d) Úplné řešení (vlastní; matice $l$, $p$ převzaty 1:1 ze slidu 46)

(a) Inicializace: $l^0$ přesně jak je uvedeno u slidu 46 výše — váhy hran, $\infty$ mimo hrany a $\infty$ i na diagonále; $p_{ij} := i$ pro všechna $(i,j)$.

(b) Čtení diagonály výsledné matice $l$ (viz výše): $\operatorname{diag}(l) = (10,\ 0,\ 1,\ 1,\ 0)$. Záporné číslo na diagonále není → graf nemá záporný cyklus a hodnoty jsou délky nejkratších cyklů přes jednotlivé vrcholy.

  • Minimální cyklus: váha $0$ (vrcholy 2 a 5). Rekonstrukce z řádku 2: $p_{22} = 5$ → poslední hrana $(5,2)$; $p_{25} = 2$ → úsek $2 \to 5$ je přímá hrana. Cyklus $2 \to 5 \to 2$, váha $2 + (-2) = 0$ ✓.
  • Minimální nenulový cyklus: váha $1$ (vrcholy 3 a 4). Z řádku 4: $p_{44} = 2$ → poslední hrana $(2,4)$; $p_{42} = 3$ → před ní hrana $(3,2)$; $p_{43} = 4$ → úsek $4 \to 3$ je přímá hrana. Cyklus $4 \to 3 \to 2 \to 4$, váha $4 + (-5) + 2 = 1$ ✓ (z řádku 3 vyjde tentýž cyklus posunutý: $3 \to 2 \to 4 \to 3$).
  • Pro úplnost vrchol 1: $l_{11} = 10$ = cyklus $1 \to 5 \to 1$ ($4 + 6$) — nejdražší „nejlevnější cyklus přes vrchol“.

Pozor na interpretaci: $l_{55} = 0$ neznamená „vzdálenost z 5 do 5 je nula“ ve smyslu prázdné cesty — s touto inicializací je to délka skutečného cyklu $5 \to 2 \to 5$. Přesně proto slide 45 varuje, že $l^n_{ii}$ se nemá číst jako vzdálenost.

← Předchozí L2.13 · SP v DAG v O(V+E)