Honlapja Diákolimpia programozás
Grafikonok: megtalálni a legrövidebb utat
Ez a rész a súlyozott irányított gráf. Egy irányítatlan gráf lehet tekinteni, mint egy speciális esete orientált, és multigráfokra helyettesítik a hagyományos, és helyébe a multirebra legolcsóbb borda.
A legrövidebb út két csúcs között az úgynevezett út között, hogy a súlyok összege az élek ide tartozó útvonal minimális.
Vegye figyelembe, hogy egyes csomópontok között nem lehet a legrövidebb utat. Ez akkor lehetséges, ha van egy út között, amely negatív tömeg ciklusban. Áthaladó ez a ciklus tudjuk a végtelenségig, hogy csökkentsék a teljes súlya a lánc.
Ha egy parancsikont létezik, és van egyszerű legrövidebb út összekötő a vertex adatok (például, ha a kezdeti dobja minden ciklus hossza nulla).
Sok Diákolimpia problémák szűkülnek le, hogy megtalálják a legrövidebb utat. Általában úgy a következő probléma: adott egy gráf súlyokkal élek - nem negatív számok, szeretné megtalálni a legrövidebb utat két csúcs között. Ezt úgy oldják meg, Dijkstra algoritmus. Ha a grafikon a negatív tömeg tartalmazhat bordák, alkalmazzák Bellman-Ford algoritmus. Azt is lehetővé teszi, hogy meghatározza, hogy van egy negatív ciklust a grafikonon. Ha szeretné megtalálni a legrövidebb utat az összes pár csúcsot, akkor alkalmazza az algoritmus a Floyd-Uorshella.
Ebben a részben, azt feltételezzük, hogy ha a távolság a (u, v) = inf (végtelen), majd a grafikon nincs út között (u, v). INF állandó érték legyen elég nagy ahhoz, de célszerű választani úgy, hogy például a kifejezés INF + INF nem túlcsordulás.
szomszédsági mátrix a következő lesz: a_uv = 0, ha u = v, különben a hossza a szélek (u, v), ha létezik, különben a INF.
Dijkstra algoritmusa
Dijkstra algoritmus lehetővé teszi, hogy megtalálja a legrövidebb utat egy adott csúcsból az összes többi csúcs a gráfban. Az algoritmus az alábbi lépéseket:
- Tedd minden csúcs (kivéve az eredeti), a távolságot dist (v) = inf, a kezdeti dist (start) = 0.
- Válassza jelzetlen csúcsok v, minimális távolságot. Ha egy ilyen csúcs nincs, majd kilép.
- Mark v.
- Minden jelöletlen csúcsok szomszédosak v, próbálja meg javítani a távolság becslésére.
- Vissza a 2. lépéshez.
Végrehajtás Java:
0000: int INF = egész. MAX_VALUE / 2; // „Végtelen”
0001: int vNum; // csúcsok száma
0002: int [] [] gráf; // szomszédsági mátrix
0003:
0004 / * a Dijkstra O (V ^ 2) * /
0005: void dijkstra (int start) <
0006: logikai [] használt = new Boole [vNum]; // tömb jelek
0007: int [] ker = new int [vNum]; // tömb hossza. dist [V] = minimalnoe_rasstoyanie (start, v)
0008:
0009: töltse (dist INF.); // ustanaavlivaem távolság minden csúcsainak INF
0010: dist [Start] = 0; // beállítani a kezdeti csúcs 0
0011:
0012: for (;;) <
0013: int v = - 1;
0014: az (int NV = 0; nv dist [nv])) // választhat a legközelebb jelzetlen csúcsok
0016: v = nv;
0017: Ha a (V == - 1) break; // legközelebb vertex nem talált
0018: használt [V] = true; // nyomoktói
0019: az (int NV = 0; nv
Megjegyezzük, hogy algoritmust már csak az ára a legrövidebb utat, és nem az út csúcsai között érdekes számunkra. Tény, hogy ez elég gyakran, de ha azt szeretnénk, hogy megtaláljuk a módját, akkor Dijkstra algoritmus módosítani kell. Bemutatjuk egy másik jellemzője - előző (v) = p - vertex, ahonnan a távolság javult, hogy v 4. lépésben, az eredeti algoritmus. Sőt, ha kombinálják a legrövidebb út a kezdeti csúcs, alkotnak egy fa. A tetején minden fa a gyökér kivételével pontosan egy őse. Végén az algoritmus, előző (v) - és ez őse. Ismerve az ősök, könnyen kinyerhető és maga az út.
Legyen V - a csúcsok száma, E - élek számát. Megjegyezzük, hogy az aszimptotikus viselkedését a algoritmus O (V ^ 2). De lemerült grafikonok lehet módosítani Dijkstra algoritmus. Először is, ha elvetjük a szomszédsági mátrix, és térjen át a listákat, a relaxációs igényel csak O (E) műveleteket. Ahhoz, hogy gyorsítsa fel a legközelebbi csúcs elérése speciális adatszerkezetek kell alkalmazni (például RMQ vagy halom). Ezután megkapjuk a aszimptotikus viselkedésének O (ElogV).
Végrehajtása Dijkstra algoritmus RMQ Java:
0000: int INF = egész. MAX_VALUE / 2; // „Végtelen”
0001: int vNum; // csúcsok száma
0002: MultiList gráf; // Leírás Count
0003:
0004 / * a Dijkstra O (E log V) * /
0005: void dijkstraRMQ (int Start int végén.) <
0006: logikai [] használt = new Boole [vNum]; // tömb jelek
0007: int [] Előző = new int [vNum]; // tömb ősök
0008: int [] ker = new int [vNum]; // tömb távolságok
0009: RMQ RMQ = új RMQ (vNum); // RMQ
0010:
0011: / * * inicializálás /
0012: töltse (Előző - 1.);
0013: töltse (dist INF.);
0014: RMQ. set (. indul ker [Start] = 0);
0015:
0016: for (;;) <
0017: int v = RMQ. minIndex (); // választhat a legközelebb vertex
0018: Ha a (V == - 1 || v == végén) break; // ha nem található, vagy a vége, akkor megy
0019:
0020: használt [V] = true; // címke a kijelölt csúcsok
0021: RMQ. set (v INF.); // kiürítése és értéket RMQ
0022:
0023: a (. Int i = gráf fej [V]; i = 0; i = gráf következő [i] ..) 0024: int nv = grafikon. Vert [i];
0025: int költség = grafikon. költsége [i];
0026: ha a (használt [NV]. dist [nv]> dist [V] + költség) 0027: RMQ. set (. nv ker [nv] = dist [V] + költség); // javítsa
0028: Előző [NV] = v; // címke az ős
0029>
0030>
0031>
0032:
0033: / * visszaállítása az utat * /
0034: Stack stack = új Stack ();
0035: az (int v = végén; v = - 1; v = Előző [v].) <
0036: verem. nyomja (V);
0037>
0038: int [] sp = new int [verem. mérete ()];
0039: az (int i = 0; i 0; v / = 2) <
0088: int L = 2 * v;
0089: int r = l + 1;
0090: ha a (Val [l]
Bellman-Ford algoritmus
Bellman-Ford algoritmus nem túl gyors (O (VE)), de a futó grafikonok és negatív élek. Az algoritmus igen egyszerű: a távolság a üzembe az eredeti csúcsok - 0 a maradék INF, akkor V - 1-szer, hogy mindenféle relaxációs (lesznek pontosan E). Megteheti optimalizálás, ha az aktuális lépés nem képes semmilyen relaxáció - stop. Ha az (V - 1) -edik iterációs végezhet relaxáció, a grafikon negatív tömeg ciklus (megtalálja az kifejezetten tárolva ősei).
0000: int INF = egész. MAX_VALUE / 2; // „Végtelen”
0001: int vNum; // csúcsok száma
0002: MultiList gráf; // Leírás Count
0003:
0004 / * Bellman-Ford algoritmus O (VE) * /
0005: void fordBellman (int start) <
0006: int [] ker = new int [vNum]; // tömb távolságok
0007: töltse (dist INF.); //
0008: dist [Start] = 0; // inicializálása
0009: (int it = 1; ez
Az algoritmus a Floyd-Uorshella
Ez az algoritmus megállapítja kratayshie közötti távolságokat az összes pár csúcsok O (V ^ 3). Algoritmus leírása: rögzítsük a felső k, majd végiglépdelni lehetséges pár csúcsok (i, j), és ha a_ij> a_ik + a_kj, majd tegye a_ij = a_ik + a_kj.
0000: int INF = egész. MAX_VALUE / 2; // „Végtelen”
0001: int vNum; // csúcsok száma
0002: int [] [] gráf; // szomszédsági mátrix
0003:
0004 / * Algoritmus Floyd-Uorshella O (V ^ 3) * /
0005: void floydWarshall () <
0006: int [] [] ker = new int [vNum] [vNum]; // dist [i] [j] = minimalnoe_rasstoyanie (i, j)
0007: az (int i = 0; i