LINUXSOFT.cz Přeskoč levou lištu
Uživatel: Heslo:  
   CZUKPL

> Grafy a grafové algoritmy I

Tento článek pojednává o grafech a algoritmech s nimi spojenými. Článek začíná teorií, ve které jsou zavedeny některé důležité pojmy, včetně definice samotného grafu. Poté následuje algoritmus pro zjištění metriky grafu a nakonec je popsán a ukázán Dijkstrův algoritmus, který slouží k nalezení nejkratších cest.

8.2.2011 19:00 | Petr Sklenička | Články autora | přečteno 16796×

Úvod do teorie - základní pojmy

Hned v úvodu začneme tím, co je to vlastně graf. Jednoduše řečeno, není to nic jiného, než množina vrcholů a hran, přičemž jednotlivé vrcholy jsou navzájem hranami spojeny a to tak, že každá hrana spojuje právě dva vrcholy. Je však nutné popsat graf trochu lépe, proto tedy správná definice grafu zní:

Obyčejný, nebo též jednoduchý, neorientovaný graf je uspořádáná dvojice G = (V, E), kde V je množina vrcholů a E je množina hran - množina vybraných dvouprvkových podmnožin množiny vrcholů.
Ukázka obyčejného grafu
Na obrázku je uvedena ukázka grafu, který má 7 vrcholů a 9 hran. Je vidět, že každá hrana spojuje právě dva různé vrcholy. Takovým vrcholům se pak říká sousední. Jako příklad sousedních vrcholů lze uvést třeba vrcholy 2 a 6, 0 a 5 apod. Vrcholy 0 a 1 ale mezi sebou hranu nemají, tudíž nejsou sousední. To však ještě nutně nemusí znamenat, že se z jednoho vrcholu do druhého nejde dostat. Z vrcholu 0 je možné jít do vrcholu 4 a z toho pak do vrcholu 1. Tím jsme vlastně našli jednu cestu, což je další pojem, který se v souvislosti s grafy používá.

Cesta délky n má (n + 1) vrcholů, spojených za sebou n hranami.

Cesta, kterou jsme si uvedli my, má tedy délku 2. Určitě ale není těžké najít jinou cestu délky 2. Je snad tedy jasné, že cest z jednoho vrcholu do druhého může v grafu existovat více, ne jen jedna. Je to stejné jako například s městy. Z Prahy do Ostravy můžete jet přímo po dálnici, což bude asi nejkratší cesta (nejkratší ve smyslu vzdálenosti), ale také můžete jet přes České Budějovice a cesta bude delší. Příklad, který jsem uvedl, lze snadno převést na graf, kde města budou vrcholy a hrany budou jednotlivé cesty. Zatím jsme ale pracovali s grafy, kde jednotlivé hrany byly stejné dlouhé. V reálném světě tomu tak samozřejmě není, vzdálenost mezi Prahou a Českými Budějovicemi je určitě jiná, než vzdálenost mezi Prahou a Ostravou. Aby se i tato skutečnost dala reprezentovat pomocí grafů, zavedl se pojem tzv. váženého grafu.

Vážený graf je graf, společně s ohodnocením svých hran reálnými čísly.

Tato definice neznamená nic jiného, než to, že se jedná o obyčejný graf, který má ale navíc u svých hran čísla, která udavájí váhu (velikost). Z toho vyplývá, že hrany v grafu mají různou velikost. Tyto grafy nám pak dávají větší možnost, jak vyjádřit něco skutečného, například již zmíněné spojení mezi městy. Na následujícím obrázku je ukázka váženého (ohodnoceného) grafu, na kterém je vyznačena nejkratší možná cesta (červenou barvou) z vrcholu 0 do vrcholu 3 - schválně si všimněte, že cesta vede přes 5 hran, přičemž je možné, najít cestu pouze přes 2 hrany, nicméně tato cesta bude delší. To je dáno tím, že v tuto chvíli nás nezajímá počet hran, ale jejich ohodnocení.
Vážený, neboli ohodnocený graf
V tomto malém grafu asi není problém během okamžiku najít nejkratší cestu z jednoho vrcholu do druhého. V mnohem větších grafech už to tak snadné není, proto k nalezení nejkratší cesty v grafu je algoritmus, konkrétně Dijkstrův algoritmus. K němu se dostaneme za chvíli, nejprve si ukážeme jednodušší algoritmus pro výpočet metriky grafu.

Metrika grafu

Dříve, než přejdeme k samotnému algoritmu, který je mimochodem poměrně jednoduchý, řekneme si, co to vlastně metrika grafu je. Není to nic jiného, než soubor vzdáleností mezi všemi dvojicemi vrcholů grafu. Je to tedy vlastně matice (dvourozměrné pole), kde prvek d[i][j] udává vzdálenost mezi vrcholy i a j. Pro názornost si uvedeme ukázku metriky grafu z předchozího obrázku.

[i][j]0123456
00613192914
160713468
21370611131
319136017195
424111701012
596131910014
61481512140

Abychom mohli napsat algoritmus, který nám dokáže metriku vypočítat, musíme nejprve do programu jako vstup zadat náš graf. Otázka je tedy jasná - jakým způsobem reprezentovat graf v paměti? Možnost není jen jedna, v tomto případě však bude nejvhodnější použít tzv. matici sousednosti. Jedná se o dvourozměrné pole (např. G), ve kterém G[i][j] = x znamená, že mezi vrcholy i a j je hrana délky x. Tam, kde hrana není, bude hodnota 0. V jazyce C++ bychom matici sousednosti zapsali takto:


const int N = 7;    // pocet vrcholu

int G[N][N];



for (int i = 0; i < N; i++)

  for (int j = 0; j < N; j++)

    G[i][j] = 0;



G[0][2] = G[2][0] = 15;

G[0][4] = G[4][0] = 2;

G[0][5] = G[5][0] = 9;

G[1][2] = G[2][1] = 7;

G[1][4] = G[4][1] = 4;

G[1][5] = G[5][1] = 6;

G[2][3] = G[3][2] = 12;

G[2][6] = G[6][2] = 1;

G[3][6] = G[6][3] = 5;

Nejprve jsme všechny hodnoty v poli nastavili na nulu, poté jsme přidali jednotlivé hrany. Zde je dobré si všimnout, že nastavíme-li hranu mezi vrcholy 0 a 2, musíme také nastavit hrany mezi vrcholy 2 a 0 - jedná se samozřejmě o tutéž hranu. V tuto chvíli máme náš graf v paměti a je možné přejít k samotnému algoritmu.

Budeme počítat metriku, čili matici, proto potřebujeme pole, které si označíme například d. Na začátku bude hodnota prvku d[i][j] udávat délku hrany mezi vrcholy i a j, nebo "nekonečno" v případě, že hrana mezi těmito vrcholy není (nekonečno budeme reprezentovat konstantou INT_MAX / 2). Poté při každém dalším kroku algoritmu se vzdálenost mezi vrcholy buď zmenší, nebo zůstane stejná (nikdy se nezvětší). My vlastně v každém kroku přidáme jeden konkrétní vrchol a zjistíme, zda je možné se díky tomuto vrcholu dostat z i do j kratší cestou.


// vypocet metriky

for (int i = 0; i < N; i++)

  for (int j = 0; j < N; j++)

    if (i == j)

      d[i][j] = 0;

    else if (G[i][j] != 0)

      d[i][j] = G[i][j];

    else

      d[i][j] = INT_MAX / 2;



for (int k = 0; k < N; k++)

  for (int i = 0; i < N; i++)

    for (int j = 0; j < N; j++)

      d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

V kódu je funkce min. Je to jednoduchá malá funkce, která vrátí menší ze dvou čísel, které má jako své parametry. Co se v kódu tedy vlastně děje? V prvních dvou cyklech dojde k nastavení počáteční metriky - tam, kde je hrana, tam se uloží její délka, jinak se uloží INT_MAX / 2. Jenom v případech kdy i je rovno j uložíme nulu, neboť vzdálenost z vrcholu a do vrcholu a je 0.

Trochu složitější je to v následujících třech cyklech. Iterační proměnná k nám vlastně symbolizuje nějaký vrchol, i a j jsou vrcholy, mezi kterými hledáme nejkratší cestu. My poté buď ponecháme vzdálenost mezi vrcholy takovou, jaká je momentálně v matici metriky, nebo na pozici d[i][j] uložíme cestu kratší, která vede právě přes vrchol k. Pro dokonalé pochopení doporučuji si algoritmus trochu projít, není nikterak složitý. Až algoritmus skončí, máme v poli d uloženou metriku grafu, čili soubor vzdáleností mezi všemi vrcholy.

Podíváme-li se na algoritmus z trochu jiného pohledu, musíme konstatovat, že implementačně není příliš složitý a zjistí nám nejkratší cesty mezi všemi vrcholy. Má však jednu (a poměrně velkou) nevýhodu - obvykle potřebujeme znát nejkratší cestu pouze mezi dvěma konrétními vrcholy, ale tento algoritmus nám vypočítá nejkratší cesty mezi všemi vrcholy, což je dosti zbytečné. Proto se tento algoritmus používá opravdu jen v konkrétních případech, kdy nás zajímají všechny vzdálenosti. V případě, že nás zajímají pouze nejkratší cesty z jednoho konkrétního vrcholu, je mnohem lepší použít Dijkstrův algoritmus.

Dijkstrův algoritmus

Tento algoritmus je sice o něco složitejší než výše uvedený, je však rychlejší. Na základě tohoto algoritmu je možné napsat program, který bude vyhledávat vlakové či autobusové spojení. Nyní se podívejme na popis, jak algoritmus funguje.

Všechny vrcholy jsou uchovávány v prioritní frontě, přičemž jsou řazené dle vzdálenosti od zdroje (zdrojem rozumíme vrchol, ze kterého hledáme cesty). V prvním průchodu má pouze zdroj vzdálenost 0, ostatní uzly mají zatím vzdálenost nekonečno (INT_MAX). Poté algoritmus vybere z fronty vrchol, který má nejvyšší prioritu, čili vrchol, který má nejmenší vzdálenost od zdroje. Tento vrchol zařadí mezi zpracované vrcholy. Následně projde všechny nezpracované sousední vrcholy tohoto zpracovaného vrcholu, přidá je do fronty a ověří, zda jsou blíže ke zdroji, než byly předtím. V případě, že zjistí, že některý sousední vrchol je nyní blíže, nastaví tomuto vrcholu novou, menší vzdálenost. Po průchodu všech sousedů se algoritmus vrací zpět na začátek. Algoritmus skončí, jakmile jsou jako zpracované označené všechny vrcholy. Poté máme k dispozici délky nejkratších cest z vrcholu, který jsme si vybrali jako zdroj.

Ukázku, jak napsat Dijkstrův algoritmus v jazyce C++, si můžete stáhnout zde. Graf je opět reprezentován pomocí matice sousednosti. Výstupem z programu jsou nejkratší vzdálenosti z vrcholu 0 do všech ostatních vrcholů (v kódu je graf, u kterého jsme výše počítali metriku). To, že algoritmus funguje správně, si tak můžete ověřit tím, že se podíváte na výstup programu a zjistíte, že je totožný s prvním (lepší je možná nultým, neboť hledáme cesty z vrcholu 0) řádkem (nebo sloupcem) matice metriky.

Verze pro tisk

pridej.cz

 

DISKUZE

Wikipedia-Dijkstrov algoritmus 10.2.2011 22:13 Tomas Hreben
  L Re: Wikipedia-Dijkstrov algoritmus 10.2.2011 23:24 Petr Sklenička
    L Re: Wikipedia-Dijkstrov algoritmus 11.2.2011 06:46 Tomas Hreben
      L Re: Wikipedia-Dijkstrov algoritmus 11.2.2011 10:48 Petr Sklenička




Příspívat do diskuze mohou pouze registrovaní uživatelé.
> Vyhledávání software
> Vyhledávání článků

12.8.2018 16:58 /František Kučera
Srpnový pražský sraz spolku OpenAlt se koná ve čtvrtek – 16. 8. 2018 od 19:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát jsou tématem srazu databáze prezentaci svého projektu si pro nás připravil Standa Dzik. Dále bude prostor, abychom probrali nápady na využití IoT a sítě The Things Network, případně další témata.
Přidat komentář

16.7.2018 1:05 /František Kučera
Červencový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 7. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát bude přednáška na téma: automatizační nástroj Ansible, kterou si připravil Martin Vicián.
Přidat komentář

18.6.2018 0:43 /František Kučera
Červnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 21. 6. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: F-Droid, aneb svobodný software do vašeho mobilu. Kromě toho budou k vidění i vývojové desky HiFive1 se svobodným/otevřeným čipem RISC-V.
Přidat komentář

23.5.2018 20:55 /Ondřej Čečák
Od pátku 25.5. proběhne na Fakultě informačních technologií ČVUT v Praze openSUSE Conference. Můžete se těšit na spostu zajímavých přednášek, workshopů a také na Release Party nového openSUSE leap 15.0. V na stejném místě proběhne v sobotu 26.5. i seminář o bezpečnosti CryptoFest.
Přidat komentář

20.5.2018 17:45 /Redakce Linuxsoft.cz
Ve čtvrtek 31. května 2018 připravuje webový magazín BusinessIT ve spolupráci s Best Online Média s.r.o. pátý ročník odborné konference Firemní informační systémy 2018. Akce proběhne v kongresovém centru Vavruška (palác Charitas), Karlovo náměstí 5, Praha 2 (u metra Karlovo náměstí) od 9:00 hod. dopoledne do cca 15 hod. odpoledne. Konference je zaměřena na efektivní využití firemních informačních systémů a na to, jak plně využít jejich potenciál. Podrobnější informace na webových stránkách konfrence.
Přidat komentář

14.5.2018 7:28 /František Kučera
Květnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 17. 5. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tentokrát na téma: Audio – zvuk v GNU/Linuxu.
Přidat komentář

7.5.2018 16:20 /František Kučera
Na stránkách spolku OpenAlt vyšla fotoreportáž Pražské srazy 2017 dokumentující srazy za uplynulý rok. Květnový pražský sraz na téma audio se bude konat 17. 5. 2018 (místo a čas ještě upřesníme).
Přidat komentář

17.4.2018 0:46 /František Kučera
Dubnový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 19. 4. 2018 od 18:00 v Kavárně Ideál (Sázavská 30, Praha), kde máme rezervovaný salonek. Tématem tohoto srazu bude OpenStreetMap (OSM) aneb svobodné mapy.
Přidat komentář

   Více ...   Přidat zprávičku

> Poslední diskuze

20.2.2018 18:48 / Ivan Majer
portal

20.2.2018 15:57 / Jan Havel
Jak využíváte služby cloudu v podnikání?

16.1.2018 1:08 / Ivan Pittner
verejna ip od o2 ubuntu

15.1.2018 17:26 / Mira Harvalik
Re: Jak udělat HTML/Javascript swiping gallery do mobilu?

30.12.2017 20:16 / Michal Knoll
odmocnina

Více ...

ISSN 1801-3805 | Provozovatel: Pavel Kysilka, IČ: 72868490 (2003-2018) | mail at linuxsoft dot cz | Design: www.megadesign.cz | Textová verze