LINUXSOFT.cz Přeskoč levou lištu

ARCHIV



   

> 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 20452×

Ú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ů

28.11.2018 23:56 /František Kučera
Prosincový sraz spolku OpenAlt se koná ve středu 5.12.2018 od 16:00 na adrese Zikova 1903/4, Praha 6. Tentokrát navštívíme organizaci CESNET. Na programu jsou dvě přednášky: Distribuované úložiště Ceph (Michal Strnad) a Plně šifrovaný disk na moderním systému (Ondřej Caletka). Následně se přesuneme do některé z nedalekých restaurací, kde budeme pokračovat v diskusi.
Komentářů: 1

12.11.2018 21:28 /Redakce Linuxsoft.cz
22. listopadu 2018 se koná v Praze na Karlově náměstí již pátý ročník konference s tématem Datová centra pro business, která nabídne odpovědi na aktuální a často řešené otázky: Jaké jsou aktuální trendy v oblasti datových center a jak je optimálně využít pro vlastní prospěch? Jak si zajistit odpovídající služby datových center? Podle jakých kritérií vybírat dodavatele služeb? Jak volit vhodné součásti infrastruktury při budování či rozšiřování vlastního datového centra? Jak efektivně datové centrum spravovat? Jak co nejlépe eliminovat možná rizika? apod. Příznivci LinuxSoftu mohou při registraci uplatnit kód LIN350, který jim přinese zvýhodněné vstupné s 50% slevou.
Přidat komentář

6.11.2018 2:04 /František Kučera
Říjnový pražský sraz spolku OpenAlt se koná v listopadu – již tento čtvrtek – 8. 11. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma umění a technologie, IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

4.10.2018 21:30 /Ondřej Čečák
LinuxDays 2018 již tento víkend, registrace je otevřená.
Přidat komentář

18.9.2018 23:30 /František Kučera
Zářijový pražský sraz spolku OpenAlt se koná již tento čtvrtek – 20. 9. 2018 od 18:00 v Radegastovně Perón (Stroupežnického 20, Praha 5). Tentokrát bez oficiální přednášky, ale zato s dobrým jídlem a pivem – volná diskuse na téma IoT, CNC, svobodný software, hardware a další hračky.
Přidat komentář

9.9.2018 14:15 /Redakce Linuxsoft.cz
20.9.2018 proběhne v pražském Kongresovém centru Vavruška konference Mobilní řešení pro business. Návštěvníci si vyslechnou mimo jiné přednášky na témata: Nejdůležitější aktuální trendy v oblasti mobilních technologií, správa a zabezpečení mobilních zařízení ve firmách, jak mobilně přistupovat k informačnímu systému firmy, kdy se vyplatí používat odolná mobilní zařízení nebo jak zabezpečit mobilní komunikaci.
Přidat komentář

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ář

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

> Poslední diskuze

31.7.2023 14:13 / Linda Graham
iPhone Services

30.11.2022 9:32 / Kyle McDermott
Hosting download unavailable

13.12.2018 10:57 / Jan Mareš
Re: zavináč

2.12.2018 23:56 / František Kučera
Sraz

5.10.2018 17:12 / Jakub Kuljovsky
Re: Jaký kurz a software by jste doporučili pro začínajcího kodéra?

Více ...

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