Drsná matematika III -- 9. demonstrované cvičení Grafy a algoritmy: cesty a souvislost v grafech Masarykova univerzita Fakulta informatiky 18. 11. 2008 Obsah přednášky Literatura Algoritmy a reprezentace grafů Domácí úlohy z minulého týdne Prohledávání do šířky a do hloubky Souvislé komponenty grafu Nejkratší cesty Metrika na grafech Dijkstrův algoritmus pro hledání nejkratších cest Plán přednáky Literatura Algoritmy a reprezentace grafů Domácí úlohy z minulého týdne Prohledávání do šířky a do hloubky Souvislé komponenty grafu Nejkratší cesty Metrika na grafech Dijkstrův algoritmus pro hledání nejkratších cest Kde je dobré číst? Jiří Matoušek, Jaroslav Nešetřil, Kapitoly z diskrétní matematiky, Univerzita Karlova v Praze, Karolinum, Praha, 2000, 377 s. Petr Hliněný, Teorie grafů, studijní materiály, http://www.fi.muni.cz/~hlineny/Vyuka/GT/ Bill Cherowitzo, Applied Graph Therory, Lecture Notes, http://www- math.cudenver.edu/~wcherowi/courses/m4408/m4408f.html Plán přednáky Literatura Algoritmy a reprezentace grafů Domácí úlohy z minulého týdne Prohledávání do šířky a do hloubky Souvislé komponenty grafu Nejkratší cesty Metrika na grafech Dijkstrův algoritmus pro hledání nejkratších cest Prohledávání v grafech Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průbehu procesu pak v každém okamžiku jsou vrcholy již zpracované, tj. ty, které jsme již při běhu algoritmu procházeli a definitivně zpracovali; aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracovávání; spící, tj. ty vrcholy, na které teprve dojde. Prohledávání v grafech Algoritmy bývají založeny na postupném prohledávání všech vrcholů v grafu. Zpravidla máme zadaný počáteční vrchol nebo si jej na začátku procesu zvolíme. V průbehu procesu pak v každém okamžiku jsou vrcholy již zpracované, tj. ty, které jsme již při běhu algoritmu procházeli a definitivně zpracovali; aktivní, tj. ty vrcholy, které jsou detekovány a připraveny pro zpracovávání; spící, tj. ty vrcholy, na které teprve dojde. Zároveň si udržujeme přehled o již zpracovaných hranách. V každém okamžiku musí být množiny vrcholů a/nebo hran v těchto skupinách disjunktním rozdělením množin V a E vrcholů a hran grafu G a některý z aktivních vrcholů je aktuálně zpracováván. Základní postup: Na počátku máme jeden aktivní vrchol a všechny ostaní vrcholy jsou spící. Základní postup: Na počátku máme jeden aktivní vrchol a všechny ostaní vrcholy jsou spící. V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme statut na aktivní. Základní postup: Na počátku máme jeden aktivní vrchol a všechny ostaní vrcholy jsou spící. V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme statut na aktivní. V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. Základní postup: Na počátku máme jeden aktivní vrchol a všechny ostaní vrcholy jsou spící. V prvním kroku projdeme všechny hrany vycházející z aktivního vrcholu a jejich příslušným koncovým vrcholům, které jsou spící, změníme statut na aktivní. V dalších krocích vždy u zpracovávaného vrcholu probíráme ty z něho vycházející hrany, které dosud nebyly probrány a jejich koncové vrcholy přidáváme mezi aktivní. Tento postup aplikujeme stejně u orientovaných i neorientovaných grafů, jen se drobně mění význam adjektiv koncový a počáteční u vrcholů. V konkrétních úlohách se můžeme omezovat na některé z hran, které vychází z aktuálního vrcholu. Na principu to ale nic podstatného nemění. Pro realizaci algortimů je nutné se rozhodnout, v jakém pořadí zpracováváme aktivní vrcholy a v jakém pořadí zpracováváme hrany z nich vycházející. V zásadě příchází v úvahu dvě možnosti zpracovávání vrcholů: 1. vrcholy vybíráme pro další zpracování ve stejném pořadí, jak se stávaly aktivními (fronta) 2. dalším vrcholem vybraným pro zpracování je poslední zaktivněný vrchol (zásobník). V prvním případě hovoříme o prohledávání do šířky, ve druhém o prohledávání do hloubky. Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: Na první pohled je zřejmá role volby vhodných datových struktur pro uchovávání údajů o grafu. Hranový seznam umožňuje projít všechny hrany vycházející z právě zpracovávaného vrcholu v čase lineárně úměrném jejich počtu. Každou hranu přitom diskutujeme nejvýše dvakrát, protože má právě dva konce. Zjevně tedy platí: Theorem Celkový čas realizace vyhledávání do šířky i do hloubky v čase O((n + m) K), kde n je počet vrcholů v grafu, m je počet hran v grafu a K je čas potřebný na zpracování jedné hrany, resp. jednoho vrcholu. Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 0 0 1 1 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Ilustrace prohledávání do šířky: 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0011 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 Zakroužkovaný vrchol je ten právě zpracovávaný, modré velké puntíky jsou již zpracované uzly, čárkované červené hrany jsou již zpracované a červené drobné uzly jsou ty aktivní (poznají se také podle toho, že do nich již vede některá zpracovaná hrana). Hrany zpracováváme v pořadí orientace proti hodinovým ručkám, přičemž za ,,první bereme směr ,,kolmo dolů . Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0011 0 0 1 1 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0011 0 0 1 1 0011 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0011 0 0 1 1 0011 0011 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0011 0 0 1 1 0011 0011 0011 Totéž postupem ,,do hloubky . Všimněte si, že první krok je stejný jako v předchozím případě. 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0011 0011 0011 0 0 1 1 0 0 1 1 0 0 1 1 0011 0 0 1 1 0011 0011 0 0 1 1 0011 0011 0011 0011 Označme vrcholy v grafu K5 postupně čísly 1, 2, . . . , 5. Napište posloupnost hran grafu K5 tak, jak je bude procházet algoritmus ,,prohledávání do šířky , bude-li počátečním vrcholem vrchol 5 a hrany ze zpracovávaného vrcholu budeme procházet postupně podle velikosti druhého koncového vrcholu hrany (od nejmenšího). Souvislé komponenty grafu Definition Nechť je G = (V , E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci tak, že v w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[v] říkáme souvislé komponenty grafu G. Souvislé komponenty grafu Definition Nechť je G = (V , E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci tak, že v w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[v] říkáme souvislé komponenty grafu G. Pro orientované grafy postupujeme stejně, pouze u požadujeme aby cesta existovala z uzlu v do uzlu w nebo naopak z uzlu w do uzlu v. Souvislé komponenty grafu Definition Nechť je G = (V , E) neorientovaný graf. Na množině vrcholů grafu G zavedeme relaci tak, že v w právě když existuje cesta z v do w. Promyslete si, že tato relace je dobře definovaná a že se jedná o ekvivalenci. Každá třída [v] této ekvivalence definuje indukovaný podgraf G[v] G a disjunktní sjednocení těchto podgrafů je ve skutečnosti původní graf G. Podgrafům G[v] říkáme souvislé komponenty grafu G. Pro orientované grafy postupujeme stejně, pouze u požadujeme aby cesta existovala z uzlu v do uzlu w nebo naopak z uzlu w do uzlu v. Jinými slovy: Každý graf G = (V , E) se přirozeně rozpadá na disjunktní podgrafy Gi takové, že vrcholy v Gi a w Gj jsou spojeny nějakou cestou právě, když i = j. To jsou právě souvislé komponenty grafu G. Pro hledání všech souvislých komponent v grafu lze užít prohledávání -- dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Pro hledání všech souvislých komponent v grafu lze užít prohledávání -- dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Definition Řekneme, že graf G = (V , E) je souvislý, jestliže má právě jednu souvislou komponentu; vrcholově k­souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k - 1 vrcholů; hranově k­souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k - 1 hran. Pro hledání všech souvislých komponent v grafu lze užít prohledávání -- dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Definition Řekneme, že graf G = (V , E) je souvislý, jestliže má právě jednu souvislou komponentu; vrcholově k­souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k - 1 vrcholů; hranově k­souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k - 1 hran. Silnější souvislost grafu je žádoucí např. u síťových aplikací, kdy klient požaduje značnou redundanci poskytovaných služeb v případě výpadku některých linek (tj. hran) nebo uzlů (tj. vrcholů). Pro hledání všech souvislých komponent v grafu lze užít prohledávání -- dodatečnou informací, kterou musíme zpracovávat je, kterou komponentu aktuálně procházíme. Definition Řekneme, že graf G = (V , E) je souvislý, jestliže má právě jednu souvislou komponentu; vrcholově k­souvislý, jestliže má alespoň k + 1 vrcholů a bude souvislý po odebrání libovolné podmnožiny k - 1 vrcholů; hranově k­souvislý, jestliže bude souvislý po odebrání libovolné podmnožiny k - 1 hran. Silnější souvislost grafu je žádoucí např. u síťových aplikací, kdy klient požaduje značnou redundanci poskytovaných služeb v případě výpadku některých linek (tj. hran) nebo uzlů (tj. vrcholů). Speciální případ: 2­souvislý graf je takový souvislý graf o alespoň třech vrcholech, kdy vynecháním libovolného vrcholu nenarušíme jeho souvislost. Theorem Pro graf G = (V , E) s alespoň třemi vrcholy jsou následující podmínky ekvivalentní: G je (vrcholově) 2­souvislý; každé dva vrcholy v a w v grafu G leží na společné kružnici; Theorem Pro graf G = (V , E) s alespoň třemi vrcholy jsou následující podmínky ekvivalentní: G je (vrcholově) 2­souvislý; každé dva vrcholy v a w v grafu G leží na společné kružnici; Obecnější je tzv. Mengerova věta: Theorem Pro každé dva vrcholy v a w v grafu G = (V , E) je počet hranově různých cest z v do w roven minimálnímu počtu hran, které je třeba odstranit, aby se v a w ocitly v různých komponentách vzniklého grafu. Plán přednáky Literatura Algoritmy a reprezentace grafů Domácí úlohy z minulého týdne Prohledávání do šířky a do hloubky Souvislé komponenty grafu Nejkratší cesty Metrika na grafech Dijkstrův algoritmus pro hledání nejkratších cest Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG (v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG (v, w) = . Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG (v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG (v, w) = . Budeme v dalším uvažovat pouze souvislé grafy G. Pak pro takto zadanou funkci dG : V × V N platí obvyklé tři vlastnosti vzdálenosti: dG (v, w) 0 a přitom dG (v, w) = 0 právě, když v = w; vzdálenost je symetrická, tj dG (v, w) = dG (w, v); platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w, z platí dG (v, z) dG (v, w) + dG (w, z). Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG (v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG (v, w) = . Budeme v dalším uvažovat pouze souvislé grafy G. Pak pro takto zadanou funkci dG : V × V N platí obvyklé tři vlastnosti vzdálenosti: dG (v, w) 0 a přitom dG (v, w) = 0 právě, když v = w; vzdálenost je symetrická, tj dG (v, w) = dG (w, v); platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w, z platí dG (v, z) dG (v, w) + dG (w, z). Říkáme, že dG je metrika na grafu G. Na každém (neorientovaném) grafu definujeme vzdálenost uzlů v a w jako číslo dG (v, w), které je rovno počtu hran v nejkratší možné cestě z v do w. Pokud cesta neexistuje, píšeme dG (v, w) = . Budeme v dalším uvažovat pouze souvislé grafy G. Pak pro takto zadanou funkci dG : V × V N platí obvyklé tři vlastnosti vzdálenosti: dG (v, w) 0 a přitom dG (v, w) = 0 právě, když v = w; vzdálenost je symetrická, tj dG (v, w) = dG (w, v); platí trojúhelníková nerovnost, tj. pro každou trojici vrcholů v, w, z platí dG (v, z) dG (v, w) + dG (w, z). Říkáme, že dG je metrika na grafu G. Metrika na grafu splňuje navíc: dG (v, w) má vždy nezáporné celočíslené hodnoty; je-li dG (v, w) > 1, pak existuje nějaký vrchol z různý od v a w a takový, že dG (v, w) = dG (v, z) + dG (z, w). Každá funkce dG s výše uvedenými pěti vlastnostmi na V × V je metrikou grafu s vrcholy G. Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů ­ tzv. Dijkstrův algoritmus. Nejkratší cestu v grafu, která vychází z daného uzlu v a končí v jiném uzlu w můžeme hledat pomocí prohledávání grafu do šířky. Při tomto typu prohledávání totiž postupně diskutujeme vrcholy, do kterých se umíme dostat z výchozího vrcholu po jediné hraně, poté projdeme všechny, které mají vzdálenost nejvýše 2 atd. Na této jednoduché úvaze je založen jeden z nejpoužívanějších grafových algoritmů ­ tzv. Dijkstrův algoritmus. Tento algoritmus hledá nejkratší cesty v realističtější podobě, kdy jednotlivé hrany e jsou ohodnoceny ,,vzdálenostmi , tj. kladnými reálnými čísly w(e). Kromě aplikace na hledání vzdáleností v silničních nebo jiných sítích to mohou být také výnosy, toky v sítích atd. Vstupem algoritmu je graf G = (V , E) s ohodnocením hran a počáteční vrchol v0. Vstupem algoritmu je graf G = (V , E) s ohodnocením hran a počáteční vrchol v0. Výstupem je ohodnocení vrcholů čísly dw (v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu v0 do vrcholu v. Postup dobře funguje v orientovaných i neorientovaných grafech. Vstupem algoritmu je graf G = (V , E) s ohodnocením hran a počáteční vrchol v0. Výstupem je ohodnocení vrcholů čísly dw (v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu v0 do vrcholu v. Postup dobře funguje v orientovaných i neorientovaných grafech. Je skutečně podstatné, že všechna naše ohodnocení jsou kladná. Zkusme si rozmyslet třeba cestu P3 se záporně ohodnocenou prostřední hranou. Při procházení sledu mezi krajními vrcholy bychom ,,vzdálenost zmenšovali každým prodloužením sledu o průchod prostřední hranou tam a zpět. Vstupem algoritmu je graf G = (V , E) s ohodnocením hran a počáteční vrchol v0. Výstupem je ohodnocení vrcholů čísly dw (v), která udávají nejmenší možný součet ohodnocení hran podél cest z vrcholu v0 do vrcholu v. Postup dobře funguje v orientovaných i neorientovaných grafech. Je skutečně podstatné, že všechna naše ohodnocení jsou kladná. Zkusme si rozmyslet třeba cestu P3 se záporně ohodnocenou prostřední hranou. Při procházení sledu mezi krajními vrcholy bychom ,,vzdálenost zmenšovali každým prodloužením sledu o průchod prostřední hranou tam a zpět. U orientovaných grafů bude algoritmus fungovat, pokud graf nebude obsahovat kružnici se záporným součtem ohodnocení jejích hran. Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d(v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu v0. Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d(v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu v0. Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d(v) = dw (v). Dijkstrův algoristmus vyžaduje jen drobnou modifikaci obecného prohledávání do šířky: U každého vrcholu v budeme po celý chod algoritmu udržovat číselnou hodnotu d(v), která bude horním odhadem skutečné vzdálenosti vrcholu v od vrcholu v0. Množina již zpracovaných vrcholů bude v každém okamžiku obsahovat ty vrcholy, u kterých již nejkratší cestu známe, tj. d(v) = dw (v). Do množiny aktivních (právě zpracovávaných) vrcholů W zařadíme vždy právě ty vrcholy y z množiny spících vrcholů Z, pro které je d(y) = min{d(z); z Z}. Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. Iniciační krok: Nastavíme hodnoty u všech v V , d(v) = 0 pro v = v0 pro v = v0, nastavíme Z = V , W = . Dijkstrův algoritmus Předpokládáme, že graf G má alespoň dva vrcholy. Iniciační krok: Nastavíme hodnoty u všech v V , d(v) = 0 pro v = v0 pro v = v0, nastavíme Z = V , W = . Test cyklu: Pokud není ohodnocení všech vrcholů y Z rovno , pokračujeme dalším krokem, v opačném případě algoritmus končí. Aktualizace statutu vrcholů: Najdeme množinu N všech vrcholů v Z, pro které d(v) nabývá nejmenší možné hodnoty = min{d(y); y Z}; posledně zpracované aktivní vrcholy W přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme W = N a odebereme je ze spících, tj. množina spících bude nadále Z \ N. Aktualizace statutu vrcholů: Najdeme množinu N všech vrcholů v Z, pro které d(v) nabývá nejmenší možné hodnoty = min{d(y); y Z}; posledně zpracované aktivní vrcholy W přesuneme do množiny zpracovaných a za nové aktivní vrcholy zvolíme W = N a odebereme je ze spících, tj. množina spících bude nadále Z \ N. Tělo hlavního cyklu: Pro všechny hrany v množině EWZ všech hran vycházejících z některého aktivního vrcholu v a končících ve spícím vrcholu y opakujeme: Vybereme dosud nezpracovanou hranu e EWZ ; Pokud je d(v) + w(e) < d(y), nahradíme d(y) touto menší hodnotou a jako předchůdce uzlu y označíme uzel v. Theorem Pro všechny vrcholy v v souvislé komponentě vrcholu v0 najde Dijsktrův algoritmus vzdálenosti dw (v). Vrcholy ostatních souvislých komponent zůstanou ohodnoceny d(v) = . Algoritmus lze implementovat tak, že ukončí svoji práci v čase O(n log n + m), kde n je počet vrcholů a m je počet hran v grafu G.