Algoritmus a legrövidebb út
Algoritmus a legrövidebb út
Az eredmény a legrövidebb út keresési algoritmus egy sorozata összekötő élek két meghatározott csúcsokat, és amelynek a legrövidebb hosszúságú körében az összes ilyen szekvenciák.
Első pillantásra úgy tűnik, hogy tudjuk használni az algoritmus megépítésének MOU csepp extra bordák, majd megteszi az utat, amely összeköti egy adott csomópont a felépített feszítőfa. Sajnos, az ilyen lépések nem mindig vezetnek a kívánt eredményt.
Emlékezzünk, hogy az algoritmus építésére a memorandum keresi, egy fa egy minimális összsúlyú az uszonyok. Vegyük például, hogy „lezárja” a grafikon, azaz egy grafikont, amelyben az első csúcs csatlakozik a második, a második - a harmadik, és így tovább, és az utolsó csúcs viszont csatlakozik az első. Egy ilyen görbét egyszerűen egy gyűrű, amelyben minden csúcs össze van kötve két másik. Egy példa egy ilyen gráf hat csúcsok ábrán látható. 1 (a).
Felhívjuk figyelmét, hogy a tömeg minden éle egyenlő 1, kivéve az összekötő él csúcsokat A és B, amelynek tömege egyenlő 2 Egy algoritmust szerkesztett minimális feszítőfa kiválasztja az összes széleit súlya 1, öntsük csak az él súlyát 2. Ez azonban azt jelenti, hogy az út a-ból b a minimális feszítőfa át kell haladnia az összes többi csúcsot, és annak hossza megegyezik az 5. (ábra. 1 (b)). Nyilvánvaló, hogy nem a legrövidebb, mint az eredeti gráf csúcsai az A és B van összekötve egy él hossza 2.
Dijkstra algoritmusa
A mohó algoritmus építésére minimális feszítőfa nem alkalmas, hogy megtalálják a legrövidebb utat két csúcs között az egyes műveleteket, mivel figyelembe véve csak a hossza az egyik széle. Ha megváltoztatjuk úgy, hogy amikor kiválasztja az élek, ami a felni, ő választotta ki a borda, amely része a legrövidebb út az egész utat a kezdeti csúcs, megkapjuk a kívánt eredményt. Pontosabban, ez a módosított algoritmust mutatjuk be. A 2. ábra egy példát az algoritmus végrehajtásával. Az algoritmus fut ugyanazon a grafikonon (ábra. 2 (a) pont), hogy az algoritmus építésére minimális feszítőfa, és nézzük meg a legrövidebb utat A-tól G
Az elején a csúcs, már négy lehetséges szélét. A négy szélét AB a legrövidebb él. Ezért hozzá a fa tetejére, B (ábra. 2 (c) pont), és hogy hogyan kell frissíteni a készlet utak. A már beépített fa most már csatlakozik a tetejére E és G és ezért hozzá kell adni a szegély. Továbbá meg kell nézni a vertex D, és hasonlítsa össze a közvetlen út, hogy egy, amelynek hossza megegyezik a 7. egy kis kitérőt a B csúcs, amelynek hossza megegyezik 8. Közvetlen út rövidebb, ezért rendelt nem kell változtatni a D borda. Most tanulmányozza a rendelkezésre álló lehetőségeket, azt látjuk, hogy ez a legrövidebb út-ból C hosszúságú 4. Él rövidebb, de úgy véljük, a teljes hossza az út-tól, és egy út vezet az E, a hossza 5. Most a legrövidebb út fa add vertex C (ábra. 2 (d)). Nézzük a grafikonon azt látjuk, hogy tudunk menni a tetejére F a C csúcsból, de ez az út hossza egyenlő 10 - több, mint a közvetlen útvonal és F, így a változás nem történik egy sor utak.
Ábra. 2 (g) most már akár ki egy utat A-tól F, olyan út A-tól E, áthalad a B csúcs: mindkettő hossza 5. Melyik a pályák lesz kiválasztva az a program végrehajtását módszertől függ adattárolásra ott. Mi csak találkozott kell hozzá egy csúcsot, akkor mindig kiválasztani a legjobb, hogy a címke az első a lexikográfiai sorrendben.
Az eredmény egy olyan helyzet, ábra. 2 (d). Hozzátéve, hogy a fák tetején E nem változtatja meg a többi a linkeket, így most már hozzá egy vertex F, és kap egy képet a szám. 2 (e). Megjegyzendő, hogy bár a kiegészítéssel, a vertex F és megváltoztatta a bordái közé, ami a D, ha elkezdtük a F, mindegy, a következő lépésben azt kell hozzá E.
Ábra. 2 (e) azt mutatja, hogy az elérési utat a tetején D rövidebb, mint az utat, hogy a tetején G. Ezért hozzá, hogy a tetején a fa D és kapjuk a ábrán látható helyzet. 2 (g). Továbbra is hozzá csak fel G, és ennek eredményeként megkapjuk a legrövidebb út fa ábrából. 2 (h). A hossza a legrövidebb út-tól G egyenlő 10.
A példa ábra. 2, mi foglalkozunk a teljes fa legrövidebb út a cél csúcsa G lett adva az utolsó fát. Ha megvan neki, mielőtt az algoritmus volna azonnal befejezte munkáját. Előfordulhatnak olyan helyzetek, amikor mi érdekli a legrövidebb út egy adott csúcsból az összes többi. Ha például van dolgunk, egy kis számítógépes hálózat, adatátviteli sebesség között a csomópontokat, amelyek megközelítőleg állandó, akkor az egyes számítógépek a hálózaton, tudjuk választani a legrövidebb út az egyes más számítógépekre. Ezért, ha szükséges, az üzenetet, hogy az egyetlen dolog, amire szükségünk van, hogy kihasználják előszámítása a lehető leghatékonyabb módon.