Problém nejkratší cesty

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 20. srpna 2021; kontroly vyžadují 4 úpravy .

Problém nejkratší cesty je problém najít nejkratší cestu (řetězec) mezi dvěma body (vrcholy) na grafu , ve kterém je minimalizován součet vah hran , které cestu tvoří.

Problém nejkratší cesty je jedním z nejdůležitějších klasických problémů v teorii grafů . Dnes je známo mnoho algoritmů pro jeho řešení .

Tento problém má jiná jména: problém minimální cesty nebo v zastaralé verzi problém dostavníku.

Význam tohoto úkolu je dán jeho různými praktickými aplikacemi . Například navigátoři GPS hledají nejkratší cestu mezi výchozím bodem a cílem. Křižovatky fungují jako vrcholy a silnice jsou hrany, které leží mezi nimi. Pokud je součet délek silnic mezi křižovatkami minimální, pak je nalezená cesta nejkratší.

Definice

Problém nalezení nejkratší cesty v grafu lze definovat pro neorientovaný , řízený nebo smíšený graf. Dále se budeme zabývat zadáním problému v nejjednodušší podobě pro neorientovaný graf. U smíšeného a orientovaného grafu musí být navíc zohledněny směry hran.

Graf je soubor neprázdné množiny vrcholů a hran (množiny dvojic vrcholů). Dva vrcholy v grafu sousedí, pokud mají společnou hranu. Cesta v neorientovaném grafu je posloupnost vrcholů , která sousedí s for . Taková cesta se nazývá cesta délky od vrcholu k ( udává číslo vrcholu cesty a nemá nic společného s číslováním vrcholů na grafu). $P=(v_{1},v_{2},\ldots ,v_{n})\in V\times V\times \ldots \times V$ $v_{i}$ $v_{{i+1}}$ $1\leq i<n$ $P$ $n$ $v_{1}$ $v_{n}$ $i$

Dovolit být hrana spojující dva vrcholy: a . Je dána váhová funkce , která mapuje hrany na jejich váhy, jejichž hodnoty jsou vyjádřeny jako reálná čísla, a neorientovaný graf . Pak bude nejkratší cesta z vrcholu k vrcholu cesta (kde a ), která má minimální hodnotu součtu . $e_{{i,j}}$ $v_{i}$ $v_{j}$ $f:E\rightarrow {\mathbb {R}}$ $G$ $proti$ $proti'$ $P=(v_{1},v_{2},\ldots ,v_{n})$ $v_{1}=v$ $v_{n}=v'$ $\sum _{{i=1}}^{{n-1}}f(e_{{i,i+1}}).$

Existují různé formulace problému nejkratší cesty:

Problém nejkratší cesty k danému cíli. Je nutné najít nejkratší cestu k danému cílovému vrcholu t, který začíná v každém z vrcholů grafu (kromě t). Změnou směru každé hrany patřící do grafu lze tento problém zredukovat na problém jediného počátečního vrcholu (ve kterém se provádí hledání nejkratší cesty z daného vrcholu ke všem ostatním).
Problém nejkratší cesty mezi danou dvojicí vrcholů. Je potřeba najít nejkratší cestu z daného vrcholu u do daného vrcholu v.
Problém nejkratší cesty mezi všemi dvojicemi vrcholů. Je nutné najít nejkratší cestu z každého vrcholu u ke každému vrcholu v. Tento problém lze také vyřešit pomocí algoritmu navrženého pro řešení problému jednoho zdrojového vrcholu, ale obvykle je vyřešen rychleji.

V různých formulacích úlohy mohou hrát roli délky hrany nejen samotné délky, ale také čas, náklady, výdaje, množství vynaložených zdrojů (materiálové, finanční, palivo a energie atd.) popř. další charakteristiky spojené s průchodem každé hrany. Problém tak nachází praktické uplatnění ve velkém množství oblastí (informatika, ekonomie, geografie atd.).

Problém nejkratší cesty podléhá dalším omezením

S problémem nejkratší cesty se velmi často setkáváme v situaci, kdy je třeba vzít v úvahu další omezení. Jejich přítomnost může výrazně zvýšit složitost úkolu [1] . Příklady takových úkolů:

Nejkratší cesta procházející danou množinou vrcholů. Lze uvažovat o dvou omezeních: nejkratší cesta musí procházet vybranou množinou vrcholů a nejkratší cesta musí obsahovat co nejméně nevybraných vrcholů. První z nich je dobře známá v teorii operačního výzkumu [2] .
Minimální pokrytí vrcholů orientovaného grafu cestami. Provádí se hledání minimálního počtu cest pokrývajících graf, konkrétně podmnožiny všech cest tak, aby každý vrchol orientovaného grafu patřil alespoň jedné takové cestě [3] .
Problém požadovaných cest. Je požadováno najít sadu st cest s minimální mohutností tak, aby pro kteroukoli existovala cesta , která ji pokrývá. je množina některých cest v orientovaném grafu G [4] . $P={p_{1},\tečky ,p_{m}}$ $t_{i}\v R$ $p_{j}\v P$ $R={t_{1},\tečky ,t_{k}}$
Minimální pokrytí oblouků orientovaného grafu cestami. Problém je najít minimální podmnožinu všech cest z hlediska počtu cest tak, aby každý oblouk patřil alespoň jedné takové cestě. V tomto případě je možný další požadavek, aby všechny cesty vycházely z jednoho vrcholu [5] .

Algoritmy

Vzhledem k tomu, že existuje mnoho různých formulací tohoto problému, existují nejoblíbenější algoritmy pro řešení problému nalezení nejkratší cesty v grafu:

Dijkstrův algoritmus najde nejkratší cestu z jednoho z vrcholů grafu ke všem ostatním. Algoritmus funguje pouze pro grafy bez hran se zápornou váhou [6] .
Algoritmus Bellman-Ford najde nejkratší cesty z jednoho vrcholu grafu ke všem ostatním ve váženém grafu. Váhy hran mohou být záporné.
Algoritmus hledání A* najde cestu z jednoho vrcholu (začátek) do druhého (cíl, konec) s nejnižšími náklady pomocí prvního vyhledávacího algoritmu s nejlepší shodou v grafu.
Floyd-Warshallův algoritmus najde nejkratší cesty mezi všemi vrcholy váženého orientovaného grafu [6] .
Johnsonův algoritmus najde nejkratší cesty mezi všemi dvojicemi vrcholů ve váženém orientovaném grafu.
Leeův algoritmus (vlnový algoritmus) je založen na metodě prohledávání do šířky. Najde cestu mezi vrcholy s a t grafu (s není totéž jako t) obsahující minimální počet mezilehlých vrcholů (hran). Hlavní aplikací je sledování elektrických spojů na čipech mikroobvodů a na deskách plošných spojů . Používá se také k nalezení nejkratší vzdálenosti na mapě ve strategických hrách.
Nalezení nejkratší cesty na základě Kildalova algoritmu [7] .

Práce (Cherkassky et al., 1993) [8] uvádí několik dalších algoritmů pro řešení tohoto problému.

Problém hledání nejkratší cesty z jednoho vrcholu ke všem ostatním

V této formulaci úlohy se provádí hledání nejkratší cesty z vrcholu v ke všem ostatním vrcholům grafu.

Nevážený orientovaný graf

Algoritmus	Složitost	Autor
Šířka první hledání	O ( V+E )

Toto je neúplný seznam a nemusí nikdy splňovat určité standardy úplnosti. Můžete jej doplnit z renomovaných zdrojů .

Orientovaný graf s nezápornými váhami

Algoritmus	Složitost	Autor
-	O ( V 2 EL )	Ford 1956
Bellman-Fordův algoritmus	O ( VE )	Bellman 1958 [9] , Moore 1957 [10]
-	O ( V 2 log V )	Danzig 1958, Danzig 1960, Minty (srov. Pollack & Wiebenson 1960), Whiting & Hillier 1960
Algoritmus Dijkstrova seznamu .	O ( V2 ) _	Leyzorek a kol. 1957 [11] , Dijkstra 1959 [12]
Dijkstrův algoritmus s modifikovanou binární haldou	O (( E + V ) log V )	-
. . .	. . .	. . .
Dijkstrův algoritmus využívající Fibonacciho haldu	O ( E + V log V )	Fridman & Tarjan 1984 [13] , Fridman & Tarjan 1987 [14]
-	O ( E log log L )	Johnson 1982, Karlsson & Poblete 1983
Gabovův algoritmus	O ( E log E / V L )	Gabow 1983, Gabow 1985
-	O ( E + V √ log L )	Ahuja a kol. 1990

Toto je neúplný seznam a nemusí nikdy splňovat určité standardy úplnosti. Můžete jej doplnit z renomovaných zdrojů .

Orientovaný graf s libovolnými váhami

Algoritmus	Složitost	Autor
Bellman-Fordův algoritmus	O ( VE )	Bellman [9] , Moore [10]

Toto je neúplný seznam a nemusí nikdy splňovat určité standardy úplnosti. Můžete jej doplnit z renomovaných zdrojů .

Problém nejkratší cesty mezi všemi dvojicemi vrcholů

Problém s nejkratší cestou mezi všemi dvojicemi vrcholů pro nevážený orientovaný graf předložil Simbel v roce 1953 [15] , který zjistil, že jej lze vyřešit lineárním počtem maticových manipulací (násobení). Složitost takového algoritmu je O ( V 4 ).

Existují také další rychlejší algoritmy pro řešení tohoto problému, jako je Floyd-Warshallův algoritmus se složitostí O ( V 3 ) a Johnsonův algoritmus (což je kombinace Bellman-Fordova a Dijkstrova algoritmu) se složitostí O ( VE + V 2 log V ).

Aplikace

Problém hledání nejkratší cesty na grafu lze interpretovat různými způsoby a aplikovat v různých oblastech. Následují příklady různých aplikací problému. Další aplikace jsou zkoumány v disciplíně, která se zabývá operačním výzkumem [16] .

Mapové služby

Algoritmy nejkratší cesty grafu se používají k nalezení cest mezi fyzickými objekty v mapových službách, jako jsou Google Maps nebo OpenStreetMap . Ve výukovém videu od Google se můžete naučit různé efektivní algoritmy, které se v této oblasti používají [17] .

Nedeterministický stroj

Pokud si představíme nedeterministický abstraktní stroj jako graf, kde vrcholy popisují stavy a hrany definují možné přechody, pak lze použít algoritmy nejkratší cesty k nalezení optimální sekvence řešení k dosažení hlavního cíle. Pokud jsou například vrcholy stavy Rubikovy kostky a hrana představuje jednu akci na kostce, pak lze algoritmus použít k nalezení řešení s minimálním počtem tahů.

Silniční sítě

Problém nalezení nejkratší cesty na grafu je široce používán při určování nejkratší vzdálenosti v silniční síti.

Silniční síť lze znázornit jako graf s kladnými váhami. Vrcholy jsou silniční křižovatky a okraje jsou silnice, které je spojují. Váhy hran mohou odpovídat délce daného úseku, času potřebnému k jeho překonání nebo nákladům na cestu po něm. Orientované hrany lze použít k zobrazení jednosměrných ulic. V takovém sloupci můžete zadat charakteristiku, která označuje, že některé silnice jsou pro dlouhé cesty důležitější než jiné (například dálnice). Byl formalizován v konceptu (myšlence) dálnic [18] .

Pro implementaci přístupu, kde jsou některé silnice důležitější než jiné, existuje mnoho algoritmů. Řeší problém najít nejkratší cestu mnohem rychleji než podobné na běžných grafech. Takové algoritmy se skládají ze dvou fází:

fázi předzpracování. Graf je předzpracován bez zohlednění počátečních a konečných vrcholů (může to trvat i několik dní, pokud pracujete s reálnými daty). Obvykle se provádí jednorázově a poté se přijatá data použijí.
fáze žádosti. Provádí se požadavek a hledání nejkratší cesty, přičemž jsou známy počáteční a konečný vrchol.

Nejrychlejší algoritmus dokáže tento problém vyřešit na silnicích Evropy nebo Ameriky ve zlomku mikrosekundy [19] .

Další přístupy (techniky), které se v této oblasti používají:

ALT
Obloukové vlajky
Hierarchie kontrakce
Směrování tranzitního uzlu
Prořezávání založené na dosahu
Značení

Podobné problémy

Existují problémy, které jsou podobné problému hledání nejkratší cesty v grafu.

Nalezení nejkratší cesty ve výpočetní geometrii (viz Euklidovská nejkratší cesta ).
Problém cestujícího prodejce . Je nutné alespoň jednou najít nejkratší cestu procházející zadanými městy (vrcholy) a poté se vrátit do původního města. Tato úloha patří do třídy NP-těžkých úloh, na rozdíl od problému hledání nejkratší cesty, kterou lze řešit v polynomiálním čase v grafech bez cyklů. Problém cestujícího prodejce je u velkých souborů dat vyřešen neefektivně.
Problém kanadského cestovatele a problém stochastické nejkratší cesty jsou zobecněním uvažovaného problému, kdy graf, který se má projet, je předem zcela neznámý a mění se v čase, nebo se další průchod grafem počítá na základě pravděpodobností.
Úkol najít nejkratší cestu při transformacích v grafu. Například změna váhy hrany nebo smazání vrcholu [20] .

Sdělení problému lineárního programování

Nechť je dán orientovaný graf ( V , A ), kde V je množina vrcholů a A množina hran, s počátečním vrcholem s , koncem t a váhami w ij pro každou hranu ( i , j ) v A . Váha každé hrany odpovídá programové proměnné x ij .

Pak je problém položen následovně: najděte minimum funkce , kde , za předpokladu, že pro všechna i a j platí následující nerovnost : $F=\součet _{{ij\in A}}w_{{ij}}x_{{ij}}$ $x_{{ij}}\geq 0$ $\sum _{j}x_{{ij}}-\součet _{j}x_{{ji}}={\begin{cases}1,&{\text{if }}i=s;\\-1 ,&{\text{if }}i=t;\\0,&{\text{ jinak.}}\end{cases}}$

Viz také

Poznámky

↑ Aplikace teorie grafů na programování, 1985 .
↑ Aplikace teorie grafů v programování, 1985 , str. 138-139.
↑ Aplikace teorie grafů v programování, 1985 , str. 139-142.
↑ Aplikace teorie grafů v programování, 1985 , str. 144-145.
↑ Aplikace teorie grafů v programování, 1985 , str. 145-148.
↑ 1 2 Diskrétní matematika. Kombinatorická optimalizace na grafech, 2003 .
↑ Aplikace teorie grafů v programování, 1985 , str. 130-131.
↑ Čerkasskij, Goldberg, Radzik, 1996 .
↑ 1 2 Bellman Richard, 1958 .
↑ 12 Moore , 1957 .
↑ M. Leyzorek, 1957 .
↑ Dijkstra, 1959 .
↑ Michael Fredman Lawrence, 1984 .
↑ Fredman Michael, 1987 .
↑ Shimbel, 1953 .
↑ Vývoj algoritmů a softwaru pro problémy plánování geometrických cest, 1996 .
↑ Rychlé plánování trasy .
↑ Dimenze dálnice, 2010 .
↑ A Hub-Based Labeling Algorithm, 2011 .
↑ Ladyzhensky Y., Popoff Y. Algorithm, 2006 .

Literatura

Evstigneev VA Kapitola 3. Iterativní algoritmy pro globální grafovou analýzu. Cesty a pokrytí // Aplikace teorie grafů v programování / Ed. A. P. Ershova. - Moskva: Věda . Hlavní vydání fyzikální a matematické literatury, 1985. - S. 138-150. — 352 s.
Alekseev V.E., Talanov V.A. Kapitola 3.4. Hledání nejkratších cest v grafu // Grafy. Výpočtové modely. Datové struktury . - Nižnij Novgorod: Vydavatelství státu Nižnij Novgorod. Univerzita, 2005. - S. 236-237. — 307 s. — ISBN 5–85747–810–8. Archivováno13. prosince 2013 naWayback Machine
Galkina V.A. Kapitola 4. Konstrukce nejkratších cest v orientovaném grafu // Diskrétní matematika. Kombinatorická optimalizace na grafech. - Moskva: Nakladatelství "Helios ARV", 2003. - S. 75-94. — 232 s. - ISBN 5-85438-069-2.
Berge K. Kapitola 7. Problém nejkratší cesty // Teorie grafů a její aplikace = Theorie des graphes et ses applications / Ed. I. A. Vainstein. - Moskva: Nakladatelství zahraniční literatury , 1962. - S. 75-81. — 320 s.
Austin Ore. Teorie grafů / Ed. I. M. Ovchinnikovová. - Vědecké nakladatelství , 1980. - 336 s. Archivováno15. prosince 2013 naWayback Machine
Vitaly Osipov, Hledání nejkratších cest v silničních sítích: Od teorie k implementaci na YouTube .
Harari F. Kapitola 2. Grafy // Teorie grafů / ed. G. P. Gavrilov - M. : Mir , 1973. - S. 27. - 301 s.
Cherkassky B. V. , Goldberg A. V. , Radzik T. Algoritmy nejkratších cest: Teorie a experimentální vyhodnocení // Math . Prog. - Springer Science + Business Media , 1996. - Sv. 73, Iss. 2. - S. 129-174. — ISSN 0025-5610 ; 1436-4646 – doi:10.1007/BF02592101
Richard Bellman. K problému se směrováním // Čtvrtletník aplikované matematiky. - 1958. - T. 16 . - S. 87-90 .
Dijkstra E. W. Poznámka ke dvěma problémům v souvislosti s grafy // Numer . Matematika / F. Brezzi - Springer Science + Business Media , 1959. - Sv. 1, Iss. 1. - S. 269-271. — ISSN 0029-599X ; 0945-3245 - doi:10.1007/BF01386390
Moore E. F. The shortest path through a blude // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2-5 April 1957) - Harvard University Press , 1959. - Vol. 2. - S. 285-292. — 345 s. - ( Annals of the Computation Laboratory of Harvard University ; Vol. 30) - ISSN 0073-0750
M. Leyzorek, RS Grey, AA Grey, WC Ladew, SR Meaker, RM Petry, RN Seitz. Vyšetřování modelových technik – první výroční zpráva – 6. června 1956 – 1. července 1957 – Studie modelových technik pro komunikační systémy . — Cleveland, Ohio: Case Institute of Technology, 1957.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacciho haldy a jejich použití ve vylepšených algoritmech optimalizace sítě (anglicky) : journal. - Ústav elektrických a elektronických inženýrů , 1984. - S. 338-346 . — ISBN 0-8186-0591-X . - doi : 10.1109/SFCS.1984.715934 . Archivováno z originálu 11. října 2012.
Michael Fredman Lawrence, Robert Andre Tarjan. Fibonacciho haldy a jejich použití ve vylepšených algoritmech optimalizace sítě // Journal of the Association for Computing Machinery : journal. - 1987. - Sv. 34 , č. 3 . - S. 596-615 . doi : 10.1145 / 28869.28874 .
Shimbel, Alfonso. Strukturální parametry komunikačních sítí // Bulletin of Mathematical Biophysics. - 1953. - T. 15 , č. 4 . - S. 501-507 . - doi : 10.1007/BF02476438 .
Sanders, Peter. Rychlé plánování trasy . – Google Tech Talk, 2009. – 23. března. . - "Šablona:Nekonzistentní citace".
Chen, Danny Z. Vývoj algoritmů a softwaru pro problémy s plánováním geometrických cest // ACM Computing Surveys : deník. - 1996. - prosinec ( roč. 28 , č. 4es ). — S. 18 . - doi : 10.1145/242224.242246 .
Abraham, Itai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. Dimenze dálnice, nejkratší cesty a prokazatelně účinné algoritmy // Symposium ACM-SIAM o diskrétních algoritmech: časopis. - 2010. - S. 782-793 .
Abraham, Itai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks . Symposium on Experimental Algorithms] (angl.) : journal. - 2011. - S. 230-241 .
Kroger, Martin. Nejkratší vícenásobná odpojená cesta pro analýzu propletenců ve dvou- a trojrozměrných polymerních systémech // Computer Physics Communications : deník. - 2005. - Sv. 168 , č.p. 168 . - str. 209-232 . - doi : 10.1016/j.cpc.2005.01.020 .
Ladyzhensky Y., Popoff Y. Algoritmus pro definování nejkratších cest mezi všemi uzly v grafu po kompresi dvou uzlů. Sborník Doněcké národní technické univerzity, Výpočetní technika a automatizace. Vol.107. Doněck (anglicky) : journal. - 2006. - S. 68-75 . .

Slovníky a encyklopedie	Britannica (online)
V bibliografických katalozích	GND : 4138403-9

Algoritmy pro vyhledávání grafů
Neinformované metody	Obousměrné vyhledávání Hledání paprskem Lexikografická šířka první hledání Šířka první hledání Vyhledávání podle nákladového kritéria Hloubka první hledání Zpětné vyhledávání Hledejte podle výstupu na vrchol Hloubkově omezené hledání Hloubkové vyhledávání s iterativním prohlubováním
Informované metody	Výstřižek alfa beta Metoda větvení a vazby Hledejte podle první nejlepší shody A* B* D* Hledání přechodového bodu IDA* Rekurzivní vyhledávání první nejlepší shody SMA*
Zkratky	Vlnový algoritmus Bellman-Fordův algoritmus Dijkstrův algoritmus Johnsonův algoritmus Levitův algoritmus Floyd-Warshall algoritmus Hledání okrajů
Minimální kostra	Borůvkův algoritmus Primův algoritmus Kruskalův algoritmus
jiný	Algoritmus Britského muzea Edmondsův algoritmus Přechod stromu Algoritmus nejbližšího souseda v problému obchodního cestujícího