![]() ![]() |
ARCHIV |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
![]() ![]() ![]() ![]() ![]() ![]() |
|
[i][j] | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
0 | 0 | 6 | 13 | 19 | 2 | 9 | 14 |
1 | 6 | 0 | 7 | 13 | 4 | 6 | 8 |
2 | 13 | 7 | 0 | 6 | 11 | 13 | 1 |
3 | 19 | 13 | 6 | 0 | 17 | 19 | 5 |
4 | 2 | 4 | 11 | 17 | 0 | 10 | 12 |
5 | 9 | 6 | 13 | 19 | 10 | 0 | 14 |
6 | 14 | 8 | 1 | 5 | 12 | 14 | 0 |
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;
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]);
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.
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.
Příspívat do diskuze mohou pouze registrovaní uživatelé. |
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ář
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?