2. nap
Indítsa el a dextre algoritmust a kiindulási pontból. Lehetséges O (N2). lehetséges O (Mlog (n)). Annak érdekében, hogy ellenőrizzük a létezést, először kitöltjük a távolsági tömböt néhány nagy konstans = INF-rel.
A csúcsok közötti távolság
Itt kell becsületesen írni egy dejkstra-t egy csomóba vagy egy készletbe. Emellett létrehozunk ősök tömbjét a szülő [v] útvonal visszaállításához. amelyben az V. csúcs őse tárolódik, ahonnan e csúcsra jöttünk. A szülő [v] -et két esetben frissítjük, amikor először jött a v-be, vagy a távoli távolság [v]. Ha az útvonal létezik, az út, hogy az idő visszaállítás tömb ősök, kezdve a felső, akár az ősök, amíg elérjük a haza. Érdemes megemlíteni, hogy itt szükség van a dextrának az algoritmusra való írására a szomszédossági listákon.
Futtassa a Ford-Bellman algoritmust. Az út nemlétezésének ellenőrzése szabványos - ha az n [it] = INF (amit eredetileg megadtunk) n iteráció után, akkor s nem halad az u-ba. Ne feledje, hogy egy végtelen rövid út csak negatív súlyciklus esetén lehet, de ez nem minden. Amellett, hogy egy ilyen ciklusnak léteznie kell, még mindig hozzáférhetőnek kell lennie a kiindulási csúcsról, és a végső csúcsnak is elérhetőnek kell lennie ebből a ciklusból. Ford-Bellman segítségével minden csúcsból egy csúcsot találunk. Például, hozzunk létre két logikai tömböt [] és pathrev []. ahol az útvonal [v] = true. ha a kiindulási ponttól v-re juthatunk. pathrev [v] = igaz. ha a v csúcsról a csúcsra jutunk. Az első tömb kitöltése mélyrehatóan keresi a forrásgráfot, és az átvitt mappát []. Most, ha van egy csúcs v. amely egy negatív ciklusba tartozik, és igaz is, hogy az út [v] · pathrev [v] = true. akkor a válasz "-", különben a Ford-Bellman algoritmus által talált távolság.
Floyd standard algoritmusa, amelyet a tegnapi előadáson elemeztek.
Hasonló probléma van a probléma a „legrövidebb út”, de itt meg kell csinálni a trükköt, mert meg kell találni, nem a legrövidebb és a leghosszabb út, meg kell változtatni a súlyokat az élek szemben - megszorozzuk -1.
Szabványos bfs egyetlen grafikonon, semmi különös, elemezve a tegnapi előadáson.
A ló legrövidebb útja Képzeljük el a sakkcellákat, mint egy gráf tetejét. Az A. B két csúcsa egymáshoz kapcsolódik, ha a ló az A-tól B-ig mozoghat. Mindegyik élnek egységnyi súlya lesz. Továbbra is futtatja a keresést a szélességben, majd állítsa vissza az elérési utat.
A két ló legrövidebb útja
A grafikon megegyezik az előző problémával. Most vonal (vektor) tárolja nemcsak a koordinátáit egy ló, és amint a koordinátáit két ló, plusz mindent, amit kell, hogy melyik a lovak jelenleg teszi a következő lépés. Kezdetben a két ló kiindulási koordinátáit, valamint néhány zászlót helyeztünk el, amely az első lovat (állapot) követi. A használt tömböt [] használjuk, ahol [x1] [y1] [x2] [y2] = true. ha korábban volt két ló helyzete, amelyben az első ló áll (x1; y1). és a második a (x2; y2) -ben. A következő lépés a keresett szélességű lesz a következő: mi vagyunk a sorban (vektor) Elérjük a következő koordináta párt, ha használják egy adott feltétel igaz, az esetek is, egyébként nézd meg, amit néhány lovak már sétál, és próbál menni a megfelelő állami, vagyis azt feltételezzük, hogy a lovak felváltva - van még egy pár koordinátáit, megnézte, és akinek a köre van változtatni a koordinátákat a ló, ha azokat az új állam, hamis, akkor életbe). Ha valamikor megtaláltuk, hogy mindkét ló koordinátái megegyeznek a végső rendeltetési helyükön, akkor megszüntetjük a bfs-t és visszaállítjuk az őseinket.
Megjegyzés: ebben a feladatban jobb tárolni az állam nem a sorban, és a vektor, és ahelyett, hogy mindeközben ezen vektor egyszerű, hiszen a vektor sokkal kényelmesebb, hogy visszaállítsa az ősök, az összes, hogy szükség lesz, hogy visszaállítsa az ősök esetén a vektor az egyes állami tárolja a szülőállomány indexét is a vektorban.
Ott csak futni bfs nem működik, ahogy bemutatjuk az éleket, amelyek súlya 0, 1, 2. Hogyan kérik a legrövidebb útvonal esetében a grafikon 0-1, megbeszéltük az előadás, de mi köze a az uszonyok tömege 2. A válasz egyszerű -, hogy megtörje a felső kétbe. Például két csúcsa van a és b. amelynek súlya kétszeres. C fiktív csúcsot fogunk alkotni. és cserélje ki a széle (a. b) tömeg kettesével bordák (a. c), és (c. b) súlya az egyik, mivel a borda tömeg kadogo 2. Ennek eredményeképpen megkapjuk a grafikon, amelynek minden élek súlya 0 vagy 1, és A probléma legrövidebb útja már a bfs-en keresztül is megtalálható. Érdemes megemlékezni, mikor helyreállítjuk az utat, a csereinket, és nem vesznek fiktív csúcsokat.
A gyökértől való távolság
Ez a feladat az utolsó, de nyilvánvalóan nem a legnehezebb, jól teljesített azoknak, akiknek elég erejük van ahhoz, hogy befejezzék az összes feladat feltételeit. A megoldás egyszerű - a bfs, a Ford Bellman, a Dijkstra, a Floyd vagy akár a rendszeres dfs is futtatható, mert a probléma egy fa. Ezután keresse meg a távolságot a csúcspontoktól a kiindulási ponttól, a dfs esetében a távolság ugyanaz, mint a fa csúcsának magassága.