A legrövidebb út probléma

A gráfelméletben a legrövidebb útprobléma az az algoritmikus probléma , hogy az egyik csúcsból a másikba keressünk egy utat úgy, hogy ezen út széleinek súlya összege minimális legyen.

A legrövidebb út problémájának változatai

Ennek a problémának sokféle változata van attól függően, hogy a gráf véges, orientált-e vagy sem, függetlenül attól, hogy minden ívnek vagy élnek van-e súlya vagy hossza. Két adott csomópont között a legrövidebb út az az út, amely minimalizálja a keresztezett ívek értékének összegét. A rövidebb út kiszámításához sok algoritmus létezik, az értékek jellegétől és az esetlegesen felmerülő további korlátozásoktól függően. Sok esetben léteznek polinomiális idő-összetettségű algoritmusok , például Dijkstra algoritmusa pozitív súlyú gráfokban. Másrészt, ha további korlátozásokat, például időablakokat adnak hozzá, a probléma NP-nehézsé válhat .

Az alkalmazás leggyakoribb példája a legrövidebb út keresése két város között. Ez a látszólag könnyű probléma, mivel egyszerűen a futástávolságok összegzéséről van szó, bonyolultabbá válik, ha le akarjuk vezetni az utazási időt, mert a forgalom intenzitása, az agglomerációk átkelésének ideje további korlátokat jelent. A ellenkezőleg, utat megállapítás egy mesterséges intelligencia probléma kapcsolódó tervezési . Ez abból áll, hogy hogyan kell mozogni egy környezetben a kiindulópont és a végpont között, figyelembe véve a különféle korlátozásokat. Nehézvé válik, amikor figyelembe kell venni különféle további korlátozásokat ( valós idejű végrehajtás , bizonytalanságok jelenléte, erőforrás-korlátok, kialakuló környezet stb.).

Ív súlya

A probléma és megoldásai mindenekelőtt a súlyok jellegétől függenek: minden ív reális szám súlyú . A figyelembe vett különböző esetek a következők: (x,y){\ displaystyle (x, y)}w(x,y){\ displaystyle w (x, y)}

• A súlyok mind pozitívak: Ebben az esetben a Dijkstra algoritmus az ívek és csúcsok gráfjának időbeli összetettségében oldja meg az adott csúcstól a többi csúcsig tartó legrövidebb út problémáját .O(m+nemnapló⁡nem){\ displaystyle O (m + n \ log n)}m{\ displaystyle m}nem{\ displaystyle n}
• A súlyok tetszőlegesek, de nincs negatív tömegű áramkör (nincs elnyelő áramkör ): Ebben az esetben a Bellman-Ford algoritmus lehetővé teszi annak tesztelését, hogy van-e elnyelő áramkör, és ilyen áramkör hiányában hogy rövidebb utat találjon az időben .O(nemm){\ displaystyle O (nm)}
• A súlyok tetszőlegesek: Ez a változat NP-kemény , amint az látható, ha figyelembe vesszük az NP-teljes Hamilton-út problémájának csökkentését, amely az ívek súlyának rögzítésében áll .-1{\ displaystyle -1}

A probléma változatai

A problémának lényegében két változata van:

Keresés egy adott csúcsból ( "  egyetlen forrás  " )

Rögzítünk egy csúcsot , a forrást vagy az origót , és minimális hosszúságú utat keresünk ettől a forrástól az összes csúcsig. A legfontosabb algoritmusok a következők s{\ displaystyle s}

• A Dijkstra algoritmusa pozitív súly esetén
• A Bellman-Ford algoritmus tetszőleges súlyok esetén.

Változatok:

• Az A * algoritmus két megadott pont közötti keresésre szolgáló heurisztikán alapuló algoritmus.
• A Viterbi algoritmus lehetővé teszi a zajos csatornán történő átvitel során felmerült hibák bizonyos mértékű kijavítását.

A kettős probléma a legrövidebb út megtalálása az összes csúcstól egy közös csúcsig (a célig ). Ezt a problémát úgy kezelik, hogy megfordítják az ívek irányát.

Az összes csúcspár keresése ( "  Összes pár  " )

Rövidebb utat vagy legalább egy ilyen út hosszát keressük az összes csúcspárra . (s,t){\ displaystyle (s, t)}

• A Floyd-Warshall algoritmust ad a mátrix a hossza a legrövidebb idő utak egy vertex grafikon , de a grafikon nem lehet szigorúan negatív tömeg áramkört. A negatív áramkör létezését a főátló negatív értékei látják.O(nem3){\ displaystyle O (n ^ {3})}nem{\ displaystyle n}
• A Johnson algoritmus negatív áramkör hiányában megoldja a problémát, és üreges grafikonokban gyorsabb lehet, mint Floyd-Warshall .

Megfogalmazás lineáris programként

A legrövidebb útprobléma lineáris optimalizálási problémaként formulázható az alábbiak szerint.

Legyen egy grafikon, két megkülönböztetett csúccsal (a forrás vagy az origó) és (a cél vagy a mosogató); megjegyezzük az íj költségét . A lineáris programot a következő változók alapján vesszük figyelembeG=(S,NÁL NÉL){\ displaystyle G = (S, A)}s{\ displaystyle s}t{\ displaystyle t}w(én,j){\ displaystyle w (i, j)}(én,j){\ displaystyle (i, j)}xénj{\ displaystyle x_ {ij}}

minimalizálni ∑énj∈NÁL NÉLw(én,j)xénj{\ displaystyle \ sum _ {ij \ in A} w (i, j) x_ {ij}}

a megszorításokkal és minden i esetében xénj≥0{\ displaystyle x_ {ij} \ geq 0}

∑jxénj-∑jxjén={1ha én=s;-1ha én=t;0ha nem.{\ displaystyle \ sum _ {j} x_ {ij} - \ sum _ {j} x_ {ji} = {\ elején {esetek} 1 & {\ text {si}} i = s; \\ - 1 & { \ text {si}} i = t; \\ 0 & {\ text {különben.}} \ end {esetben}}}

Az intuitív magyarázat az a változó, amelyet arra használnak, hogy jelezze, az ív a megtalált legrövidebb út része- e vagy sem: ez 1, ha van, és 0 egyébként. Megpróbáljuk kiválasztani a minimális összsúlyú ívkészletet, feltéve, hogy az ívek utat alkotnak s- től t-ig  ; ezt a feltételt a megszorítás képviseli, amely kifejezi, hogy az s és t kivételével bármely csúcs esetén a kiválasztott bejövő ívek számának meg kell egyeznie a kimenő ívek számával, és így a halmaz utat alakít ki s- től t-ig . xénj{\ displaystyle x_ {ij}}(én,j){\ displaystyle (i, j)}

Ennek a lineáris programnak a kettős programja az

maximalizálni yt-ys{\ displaystyle y_ {t} -y_ {s}}

a megszorításokkal

yj-yén≤w(én,j){\ displaystyle y_ {j} -y_ {i} \ leq w (i, j)} minden i-re, j .

A kettős bármilyen megvalósítható megoldása esetén a csökkentett költségek nem negatívak, és ezen csökkentett költségek mellett az A * algoritmus lényegében úgy viselkedik, mint a Dijkstra algoritmus. y{\ displaystyle y}w′(én,j)=w(én,j)-yj+yén{\ displaystyle w '(i, j) = w (i, j) -y_ {j} + y_ {i}}

A kettős program megoldása a csomópontokban rejlő potenciál, amely az ember számára Knotenpotenciális . Könnyen beláthatjuk, hogy bármely megoldás esetében a vektor is megoldás mindenre . Különösen úgy választhat , hogy . Tehát a maximalizálni kívánt érték az . y{\ displaystyle y}(yén)én∈S{\ displaystyle (y_ {i}) _ {i \ S} -ben}(yén+δ)én∈S{\ displaystyle (y_ {i} + \ delta) _ {i \ in S}}δ∈R{\ displaystyle \ delta \ in \ mathbb {R}}δ{\ displaystyle \ delta}ys=0{\ displaystyle y_ {s} = 0}maxyt{\ displaystyle \ max \; y_ {t}}

Bármely útvonal származó egy vertex , a hossza lehet becsülni vs.{\ displaystyle c}s{\ displaystyle s}v≠s{\ displaystyle v \ neq s}

w(vs.)=∑(én,j)∈vs.w(én,j)≥∑(én,j)∈vs.yj-yén=yv{\ displaystyle w (c) = \ sum _ {(i, j) \ in c} w (i, j) \ geq \ sum _ {(i, j) \ in c} y_ {j} -y_ {i } = y_ {v}}

Ez azt mutatja, hogy egy csomópont potenciálja alacsonyabb, mint az út hossza. Találunk egy optimális megoldás a kettős programot választotta, hogy az adott csomópont , mint a hossza a legrövidebb utat , hogy a célfüggvény . v≠s{\ displaystyle v \ neq s}s{\ displaystyle s}v{\ displaystyle v}w{\ displaystyle w}

Általánosított Floyd-Warshall algoritmus

A Warshall algoritmus, a Floyd-Warshall algoritmus és a McNaughton-Yamada algoritmus közötti hasonlóságot egy mögöttes algebrai struktúra, egy félgyűrű struktúrája magyarázza . Ezt az értelmezést először Claude Pair 1966-os cikkében mutatták be , majd Claude Pair és Jean-Claude Derniame könyvében vették fel. Az első angol változat csak 1974-ben jelent meg Aho, Hopcroft és Ullman könyvében. Ez felvesszük később, Gondran és Minoux például; utóbbiak Pierre Robert és Jacques Ferland 1968-as francia cikkét idézik.

A félgyűrű két bináris törvénnyel és . A törvény asszociatív, kommutatív és 0 vagy 0 értékű semleges elemet fogad el . A törvény asszociatív és disztributív . Elfogad egy semleges elemet, amelyet 1 vagy . A logikai algebra a félgyűrű felvételének , (vagy) és (és) példája . ⊕{\ displaystyle \ oplus}⊗{\ displaystyle \ otimes}⊕{\ displaystyle \ oplus}z{\ displaystyle z}⊗{\ displaystyle \ otimes}⊕{\ displaystyle \ oplus}e{\ displaystyle e}Q={0,1}{\ displaystyle Q = \ {0,1 \}}⊕=∨{\ displaystyle \ oplus = \ vee}⊗=∧{\ displaystyle \ otimes = \ ék}

Ahhoz, hogy az általánosított Floyd-Warshall algoritmus működjön, feltételeznünk kell azt is, hogy a törvény semlegessége elnyeli a törvényt . Más szavakkal, a félgyűrű bármely eleméhez igazolni kell az egyenlőséget . e{\ displaystyle e}⊗{\ displaystyle \ otimes}⊕{\ displaystyle \ oplus}x{\ displaystyle x}x⊕e=e{\ displaystyle x \ oplus e = e}

Súlyozott gráfhoz társított mátrix

Adjunk egy olyan gráfot, amelynek csúcsai vannak . Minden ívhez hozzárendel egy súlyt (hossz, távolság, forgalom sűrűsége a probléma szerint), amely egy félgyűrű (többé-kevésbé egyszerű félgyűrű a kezelendő probléma jellege szerint) eleme. ). A súlyozott gráffal társított mátrix az a mátrix, amelynek az elemének helyzete akkor van, ha az ív létezik, és különben 0 (a félgyűrű). G{\ displaystyle G}{1,...,nem}{\ displaystyle \ {1, \ dots, n \}}(én,j){\ displaystyle (i, j)}w(én,j){\ displaystyle w (i, j)}(én,j){\ displaystyle (i, j)}w(én,j){\ displaystyle w (i, j)}(én,j){\ displaystyle (i, j)}z{\ displaystyle z}

Az út súlya az ösvényt alkotó ívek súlyának szorzata félgyűrűben: vs.=(én0,én1,...,énd){\ displaystyle c = (i_ {0}, i_ {1}, \ ldots, i_ {d})}

w(vs.)=w(én0,én1)⊗w(én1,én2)⊗w(énd-1,énd){\ displaystyle w (c) = w (i_ {0}, i_ {1}) \ otimes w (i_ {1}, i_ {2}) \ otimes w (i_ {d-1}, i_ {d}) }.

A hossza a legrövidebb utat a , ebben a formalizmus az összeg a súlyok az . Ha az utak halmazát a -ig jelöljük , akkor a keresett út egy olyan út, amelynek súlya van én{\ displaystyle i}j{\ displaystyle j}én{\ displaystyle i}j{\ displaystyle j}Γén,j{\ displaystyle \ Gamma _ {i, j}}én{\ displaystyle i}j{\ displaystyle j}

⨁vs.∈Γén,jw(vs.){\ displaystyle \ bigoplus _ {c \ Gamma _ {i, j}} w (c)}.

Abban az esetben, ha és ez a minimum súlya utat összekötő , hogy . ⊕=min{\ displaystyle \ oplus = \ min}⊗=+{\ displaystyle \ otimes = +}én{\ displaystyle i}j{\ displaystyle j}

Általánosított Floyd-Warshall algoritmus

Mivel egy társult mátrix grafikonja érdekében , és azt határozza meg két sorozat mátrixok: NÁL NÉL{\ displaystyle A}nem{\ displaystyle n}nál nélén,j=w(én,j){\ displaystyle a_ {i, j} = w (i, j)}

• mátrixsorozat :NÁL NÉL(k){\ displaystyle A ^ {(k)}}

NÁL NÉL(0)=NÁL NÉL{\ displaystyle A ^ {(0)} = A} és NÁL NÉL(k)=(nál nélén,j(k)){\ displaystyle A ^ {(k)} = \ bal (a_ {i, j} ^ {(k)} \ jobb)}a .nál nélén,j(k)=nál nélén,j(k-1)⊕(nál nélén,k(k-1)⊗nál nélk,j(k-1)){\ displaystyle a_ {i, j} ^ {(k)} = a_ {i, j} ^ {(k-1)} \ oplus \ bal (a_ {i, k} ^ {(k-1)} \ otimes a_ {k, j} ^ {(k-1)} \ jobbra}} A mátrix szekvenciára olyan, hogy az elem a mátrix megegyezik a súlyok összege utak hossza legfeljebb a a .nál nélén,j(nem){\ displaystyle a_ {i, j} ^ {(n)}}NÁL NÉL(nem){\ displaystyle A ^ {(n)}}nem{\ displaystyle n}én{\ displaystyle i}j{\ displaystyle j}

• egy másik mátrixsorozat :D(k){\ displaystyle D ^ {(k)}}

dén,j(0)={jha (én,j) egy ív0ha nem {\ displaystyle d_ {i, j} ^ {(0)} = {\ begin {cases} j & {\ text {si}} (i, j) {\ text {egy ív}} \\ 0 & { \ text {különben}} \ end {esetek}}} dén,j(k)={dén,j(k-1)ha nál nélén,j(k)=nál nélén,j(k-1)dén,k(k-1)ha nem .{\ displaystyle d_ {i, j} ^ {(k)} = {\ elején {esetek} d_ {i, j} ^ {(k-1)} és {\ text {si}} a_ {i, j} ^ {(k)} = a_ {i, j} ^ {(k-1)} \\ d_ {i, k} ^ {(k-1)} és {\ text {különben}} \ vége {esetek} }.} A mátrix szekvenciára olyan, hogy az elemek rendelkeznek a értéke az index az első közbenső pontján útvonal , hogy a lépésben .dén,j(k){\ displaystyle d_ {i, j} ^ {(k)}}én{\ displaystyle i}j{\ displaystyle j}k{\ displaystyle k}

Ebből következik, hogy az első közbülső csúcs indexe a és között , a második csúcsot pedig az adja meg, hogy hol stb. dén,j(nem){\ displaystyle d_ {i, j} ^ {(n)}}én{\ displaystyle i}j{\ displaystyle j}do,j(nem){\ displaystyle d_ {p, j} ^ {(n)}}o=dén,j(nem){\ displaystyle p = d_ {i, j} ^ {(n)}}

Alkalmazások

A csúcstalálkozókhoz csatlakozó utak megléte

Ez a probléma, hogy tudjuk, bármely két csúcs, ha van egy útvonal a , vagy tudni, egy adott csúcs , a csúcsokat elérhető . Ezt a tranzitív lezárási problémát úgy fogalmazzák meg, hogy minden ívre ugyanazt a súlyt választják. (x,y){\ displaystyle (x, y)}x{\ displaystyle x}y{\ displaystyle y}s{\ displaystyle s}s{\ displaystyle s}

Az első problémát tehát a Warshall algoritmussal, a másodikat szintén egyszerű útvonalon, mélységben vagy szélességben tudjuk megoldani az s összegből.

Minimális távolság két csúcs között

Bármely csúcspár minimális távolságát a Floyd-Warshall algoritmus számítja ki, így a trópusi félgyűrűt vagy (max, +) - félgyűrűt veszi a pozitív vagy nulla valós szám fölé.

Két csúcs között maximális forgalmi kapacitású utak

Az útvonalon lehetséges forgalmi kapacitás az útvonalat alkotó ívek minimális kapacitása. A maximális kapacitáspálya maximalizálja ezt a minimumot. Kiszámoljuk az értékeket az általánosított Warshall algoritmus segítségével, és . ⊕=max{\ displaystyle \ oplus = \ max}⊗=min{\ displaystyle \ otimes = \ min}

Úthálózatok

Az úthálózat pozitív tömegű grafikonnak tekinthető. A csomópontok az útkereszteződéseket ábrázolják, és a grafikon minden íve két keresztezés közötti útszakaszhoz kapcsolódik. Az ív súlya lehet a kapcsolódó útszakasz hossza, a szakasz keresztezéséhez szükséges idő, vagy a szegmens utazásának költsége. Irányított grafikonok segítségével egyirányú utcák modellezése is lehetséges. Ezeknek a grafikonoknak különleges tulajdonságai vannak, mivel egyes ívek fontosabbak, mint mások a távolsági utazáshoz (általában autópályák). Ezt a tulajdonságot egy „  Highway Dimension  ” nevű további paraméterrel formalizálták . Ez lehetővé teszi az optimális útvonalak gyorsabb kiszámítását, mint az általános grafikonoknál. Az első ötlet az, hogy ha egyik kisvárosból a másikba akarsz menni, ami meglehetősen messze található, akkor az indulás helye közelében egy nagyvárost, a cél közelében pedig egy nagyvárost kell keresni, és össze kell kombinálni a két nagy agglomeráción keresztül.

Ezek az algoritmusok két fázisban működnek. Az első előfeldolgozási szakaszban a grafikon úgy van kialakítva, hogy lehetővé tegye a gyors lekérdezést. A második szakasz a kihallgatási szakasz; a kiindulási és a befejező csomópont ekkor ismert, és mivel a hálózat statikus, az előfeldolgozás egyszer és mindenkorra elvégezhető, és sok lekérdezéshez felhasználható.

A leggyorsabban ismert algoritmust (2011-ben) "  hub címkézésnek  " hívják , és a másodperc néhány részében kiszámítja a legrövidebb útvonalakat

Rövidebb út a dinamikus súlyokhoz

Egyes szállítási problémáknál a súlyok olyan funkciók, amelyek idővel változhatnak, hogy figyelembe vegyék például a forgalom ingadozásait. Ebben az esetben az algebrai módszert mindig úgy alkalmazzuk, hogy félgyűrűvé választjuk a dioidon növekvő endomorfizmusok félgyűrűjét , az indukált összeget és a kompozíciót termékként. Így, ha valaki a leggyorsabb útvonalat keresi egy olyan hálózatban, ahol a forgalom az indulási időpont függvényében változó, akkor alkalmazhatja a szokásos algoritmusokat úgy, hogy az egyes útvonalakat egy olyan függvény alapján értékeli, amely megadja az indulási időt. távozáskor, és figyelembe véve a távozáskor betöltött funkció minimumát. (f⊕g)(x)=f(x)⊕g(x){\ displaystyle (f \ oplus g) (x) = f (x) \ oplus g (x)}⊕{\ displaystyle \ oplus}

A legrövidebb út időbeli korlátokkal

Különösen a tömegközlekedési hálózatokban előfordul, hogy bizonyos íveket csak bizonyos időbeli korlátok között lehet megtenni (például éjszaka nem). Feltételezzük, hogy az egyes ívek utazási ideje rögzített, valamint egy időrés-készlet, ahol lehetséges ezen az úton haladni. Ezután az alábbiakban definiált időintervallumok alatt vett endomorfizmusok dioidját vesszük figyelembe: vagy az az időintervallum, ahol felülről akarunk indulni  ; akkor az az időintervallum, ahol lehetséges elérni a csatlakozó csúcsot . Más korlátozásokat hozzáadhatunk (az időközökkel való metszéspontban, bizonyos időszakok elkerülése érdekében, a derékszögű termék árkorlátozásainak hozzáadásával az idő és az ár között súlyozott min törvényszerű szállítási költségmátrixhoz). A Dijkstra algoritmus minden esetben hatékony felbontást tesz lehetővé. (én,j){\ displaystyle (i, j)}Hén,j{\ displaystyle H_ {i, j}}Dén{\ displaystyle D_ {i}}én{\ displaystyle i}τén,j(Dén)={dén,j+t|t∈Dén∩Hén,j}{\ displaystyle \ tau _ {i, j} (D_ {i}) = \ {d_ {i, j} + t | t \ D_ {i} \ cap H_ {i, j} \}}j{\ displaystyle j}én{\ displaystyle i}τ{\ displaystyle \ tau}

Valódi helyzetekben a közlekedési hálózat általában sztochasztikus és időfüggő. Valójában egy utazó, aki naponta utazik egy útvonalon, eltérő utazási időket tapasztalhat ezen az útvonalon, nemcsak a forgalom intenzitásának ingadozása, hanem olyan lokalizáltabb események miatt is, mint az útépítési területek, a rossz időjárási viszonyok, a balesetek és a jármű meghibásodása. Ezért az időbeli sztochasztikus hálózat a valós úthálózat reálisabb ábrázolása, mint egy determinisztikus hálózat. A jelentős előrelépés ellenére az optimális út meghatározása és meghatározása a sztochasztikus úthálózatokban továbbra is vitatott téma. Más szavakkal, a bizonytalanság jelenlétében nincs egy optimális út meghatározása. Az egyik lehetséges és elterjedt válasz egy olyan út, amely eléri a minimális várható utazási időt. Ennek a megközelítésnek az a legfőbb előnye, hogy lehetővé teszi a determinisztikus hálózatok számára bevezetett legrövidebb út-algoritmusok használatát a sztochasztikus hálózatban a minimális várható utazási idővel rendelkező út azonosítására.

Az optimális út azonban nem biztos, hogy kielégítő, mert ez a megközelítés nem veszi figyelembe az utazási idő változékonyságát. A probléma megoldásához egyes kutatók az utazási idő eloszlását használják az átlagérték helyett, és a teljes utazási idő valószínűség-eloszlását különféle optimalizálási módszerekkel, például dinamikus programozással és Dijkstra algoritmusával kapják meg . Ezek a módszerek sztochasztikus optimalizálást, és különösen dinamikus sztochasztikus programozást alkalmaznak a valószínűbb ívhosszú hálózatok legrövidebb útjának megtalálásához. Meg kell jegyezni, hogy a közlekedési kutatások irodalmában az utazási idő megbízhatóságának fogalmát felváltva használják az utazási idő változékonyságával, így általánosságban elmondható, hogy minél nagyobb az utazási idő változékonysága. oda-vissza.

Az utazási idő megbízhatóságának pontosabb számbavétele érdekében két általános alternatív meghatározást javasoltak az optimális út bizonytalanság alatt. Néhányan bevezették a legmegbízhatóbb út fogalmát, amelynek célja annak maximalizálása, hogy egy adott utazási költségnél időben vagy hamarabb megérkezzen. Mások az α-megbízható út fogalmát vetik fel, amely alapján az utazás költségeit minimalizálni kívánják, hogy biztosítsák az előre meghatározott időben történő megérkezés valószínűségét.

Bonyolultság

Mulmulay és Shah alacsonyabb bonyolultsági határokat adtak a legrövidebb út problémájához.

Megjegyzések és hivatkozások

1. Claude Pair, "A véges grafikonok áramlási problémáinak algoritmusairól" , P. Rosentiehl, Théorie des graphes (nemzetközi tanulmányi napok) - The Graphics Theory (internainális szimpózium) , Dunod (Párizs) és Gordon and Breach (New York),1966
2. Jean Claude Derniame és Claude Pair, A progresszió problémái a grafikonokban , Dunod (Párizs),1971, 182  p.
3. Alfred V. Aho, John E. Hopcroft és Jeffrey D. Ullman, A számítógépes algoritmusok tervezése és elemzése , Olvasás, Mass., Addison-Wesley ,1974, 470  p. ( ISBN  978-0-201-00029-0 )
4. Michel Gondran és Michel Minoux , grafikonok, dioids és félig gyűrűk: új modellek és algoritmusok , Párizs, Tec & Doc,2001, xvi + 415  p. ( ISBN  2-7430-0489-4 , SUDOC  060235101 )- Angol kiadás: (en) Michel Gondran és Michel Minoux , grafikonok, Dioids és Semirings: Új modellek és algoritmusok , Dordrecht, Springer Science & Business Media, coll.  "Operations Research / Computer Science interfészek sorozat" ( n o  41)2008, xix + 383  o. ( ISBN  978-0-387-75450-5 , zbMATH  1201.16038 , SUDOC  12874958X , online olvasás )
5. Pierre Robert és Jacques Ferland, „  A Warshall algoritmus általánosítása  ”, French Journal of Informatics and Operational Research, Red Series , t.  2, n o  1,1968, P.  71–85 ( online olvasás ).
6. Ittai Abraham, Amos Fiat, Andrew V. Goldberg és Renato Fonseca F. Werneck, „  Autópálya dimenzió, legrövidebb utak és bizonyíthatóan hatékony algoritmusok  ”, ACM-SIAM szimpózium a diszkrét algoritmusokról ,2010, P.  782-793 ( online olvasás ).
7. Ittai Abraham, Daniel Delling, Andrew V. Goldberg és Renato Fonseca F. Werneck, „Hub-Based Labeling Algorithm for the Shortest Paths on Road Networks” ” , Panos M. Pardalos és Steffen Rebennack (szerk.), Kísérleti algoritmusok (10.) Nemzetközi Szimpózium a kísérleti algoritmusokról, Kolimpari, Chania, Kréta, 2011. május 5–7. , Springer Science & Business Media,2011, 460  p. ( ISBN  9783642206610 , online olvasás ) , p.  230-241.
8. Mojtaba Rajabi-Bahaabadi , Afshin Shariat-Mohaymany , Mohsen Babaei és Chang Wook Ahn , „  Többcélú útkeresés sztochasztikus időfüggő úthálózatokban, nem domináns rendezési genetikai algoritmus alkalmazásával  ”, Expert Systems with Applications , vol.  42, n o  12, 2015, P.  5056–5064 ( DOI  10.1016 / j.eswa.2015.02.046 , online bemutató ).
9. Mohammad Hessam Olya , „  A legrövidebb út keresése kombinált exponenciális - gamma valószínűség-eloszlás ívhosszban  ”, International Journal of Operational Research , vol.  21, n o  1, 2014, P.  25–37 ( DOI  10.1504 / IJOR.2014.064020 , online előadás ).
10. Mohammad Hessam Olya , „  Dijkstra algoritmusának alkalmazása általános legrövidebb útproblémákra normál valószínűség-eloszlás ívhosszal  ”, International Journal of Operational Research , vol.  21, n o  2 2014, P.  143–154 ( DOI  10.1504 / IJOR.2014.064541 , online előadás ).
11. (in) "  Alsó határ a legrövidebb út problémájához  " , Journal of Computer and System Sciences , vol.  63, n o  21 st szeptember 2001, P.  253–267 ( ISSN  0022-0000 , DOI  10.1006 / jcss.2001.1766 , online olvasás , hozzáférés : 2018. november 8. )

(fr) Ez a cikk részben vagy egészben az angol Wikipedia "  Legrövidebb út probléma  " című cikkéből származik ( lásd a szerzők felsorolását ) .

Bibliográfia

Művek

• Jean Claude Derniame és Claude Pair, A progresszió problémái a grafikonokban , Dunod (Párizs),1971, 182  p.
• (en) Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest és Clifford Stein , Bevezetés az algoritmusokba , az MIT Press és a McGraw-Hill ,2001, 2 nd  ed. [ a kiadás részlete ] 26.2. Szakasz "A Floyd-Warshall algoritmus", p.  558–565 ; 26.4. Szakasz „Általános keretrendszer az útfeladatok megoldásához irányított gráfokban”, p.  570–576 .
• Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest , és Clifford Stein ( transz.  Angol), algoritmusok  : előadás gyakorlatokkal 957 és 158 problémákra , Dunod ,2010[ a kiadás részlete ]
  • 24. fejezet: "Egyetlen eredethez vezető legrövidebb utak"
  • 25. fejezet: "A legrövidebb utak az összes csúcspár között"
• Michel Gondran és Michel Minoux, Grafikonok és algoritmusok , Párizs, Lavoisier, koll.  "Franciaország villamos energia tanulmányai és kutatása",2004, 4 th  ed. ( 1 st  ed. 1979), XXXI + 784  o. ( ISBN  978-2-7430-1035-5 ) 2. fejezet: "A legrövidebb út probléma" 3. fejezet: "Út-algebrák és dioidok"
• en) Alexander Schrijver , kombinatorikus optimalizálás , Berlin / Heidelberg / New York, Springer,2004, 1881  p. ( ISBN  3-540-44389-4 , online olvasás ) 8. fejezet: "A legrövidebb utak: tetszőleges hosszúságok"

Cikkek

• Claude Pair: „A véges grafikonok áramlási problémáinak algoritmusairól” , P. Rosentiehl, Théorie des graphes (nemzetközi tanulmányi napok) - The Graphics Theory (internainális szimpózium) , Dunod (Párizs) és Gordon and Breach (New York),1966
• Ravindra K. Ahuja, Kurt Mehlhorn , James Orlin és Robert E. Tarjan, „  Gyorsabb algoritmusok a legrövidebb út problémájához  ”, ACM , vol.  37, n o  21990 április, P.  213–223 ( DOI  10.1145 / 77600.77615 , online olvasás ).
• Torben Hagerup, „Javított legrövidebb utak a Word RAM-on” , Ugo Montanari, José DP Rolim és Emo Welzl (szerkesztők), A 27. Nemzetközi Automatikák, Nyelvek és Programozás Kollokvium közleményei ,2000( ISBN  3-540-67715-1 , online olvasás ) , p.  61–72.
• Seth Pettie és Vijaya Ramachandran, „A  legrövidebb utak kiszámítása összehasonlításokkal és kiegészítésekkel  ”, A tizenharmadik éves ACM-SIAM szimpózium közleménye a diszkrét algoritmusokról ,2002, P.  267–276 ( ISBN  0-89871-513-X , online olvasás )
• Seth Pettie: „  Valódi súlyozott grafikonokon az összes pár legrövidebb útjainak új megközelítése  ”, Theoretical Computer Science , vol.  312, n o  1,2004. január, P.  47–74 ( DOI  10.1016 / s0304-3975 (03) 00402-x )
• Mikkel Thorup , „  Egész szám elsőbbségi sorok a csökkenés kulccsal állandó időben és az egyetlen forrás legrövidebb utak problémája  ”, Journal of Computer and System Sciences , vol.  69, n o  3,2004, P.  330–353 ( DOI  10.1016 / j.jcss.2004.04.003 , online olvasás ).
• Ryan Williams , „A  gyorsabb összes párok a legrövidebb utakat az áramkör bonyolultsága révén  ”, ACM , New York,2014, P.  664–673 ( DOI  10.1145 / 2591796.2591811 , Math Reviews  3238994 , arXiv  1312.6680 ).

Kapcsolódó cikkek

• A gráfelmélet szószedete
• A legrövidebb út algoritmusai
• Útkeresés
• Szélesség bejárási algoritmus
• Dijkstra algoritmusa
• A algoritmus *
• Bellman-Ford algoritmus
• Floyd-Warshall algoritmus
• Warshall algoritmus
• Hierarchikus összehúzódások
• IEEE 802.1aq
• Áramlási hálózat
• Euklideszi legrövidebb út  (be)
• Trópusi matematika
• Johnson algoritmusa
• Maximális áramlási probléma
• Távolság (grafikonelmélet)

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">