Az egyik csúcs közül a legrövidebb utak
Alapfogalmak
A G = (V, E) orientált gráf a V csúcsok és az ívek készletének a halmazából áll. A csúcsokat csomópontoknak is nevezik. és az ívek orientált élek. Az ívet reprezentálhatjuk rendezett párok (v, w) formájában. ahol a v csúcsot eredetnek nevezik. és w az ív vége.
Irányítatlan grafG = (V, E) egy véges csúcsok halmaza V és több élek E. Szemben az irányított gráf, ahol minden él (v, w), amely megfelel a rendezetlen pontpár: Ha a (V, W) - a nem-orientált szélét, majd ( v, w) = (w, v).
Az X csúcsról beszámolunk, hogy egy G élre esik, ha egy él a csúcsot egy másik csúcsra köti össze.
A legrövidebb út problémáján G = (V, E) orientált súlyozott gráfot kapunk, amelynek valós súlyfüggvénye w: E R
A p = (v0, v1, vk) pálya súlya az ezen a pályán beérkező élek súlyai összege:
Az u-tól v-ig terjedő legrövidebb út tömege definíció szerint,
Az u-től v-ig terjedő legrövidebb út az u-től v-ig terjedő p-ig. amelyre vonatkozóan
A gráf degeneráltnak nevezik. ha nincsenek élei.
A csúcsokat szomszédosnak hívják. ha létezik egy összekötő él.
Az üres gráf üres. Egy gráfot teljesnek neveznek, amelyben minden két csúcs szomszédos.
Olyan ciklus, amelyben minden csúcs, az első és az utolsó kivételével, párosan különböztethető meg, egyszerű ciklusnak nevezik.
Úgy tűnik, hogy a grafikon kapcsolódik. ha bármely két csúcs esetében létezik egy útvonal, amely összeköti ezeket a csúcsokat.
Negatív súlyú bordák
Néha a bordák súlya negatív lehet. Fontos, ha negatív súlyú ciklusok vannak. Ha ettől vertex s elérheti a negatív tömeg ciklus, akkor lehetőség van arra, hogy megkerülje ezt a ciklust a végtelenségig, és a tömeg mind csökken, így a legrövidebb utak nem létezik csúcsainak ebben a ciklusban: Ebben az esetben, akkor feltételezhető, hogy a tömeg egy legrövidebb út - ∞.
Ha nincs negatív súlyciklus, akkor bármelyik ciklus eldobható az út meghosszabbítása nélkül. A ciklus nélküli utak végesek, ezért a legrövidebb út súlya jól meghatározott.
Az algoritmus legrövidebb útjainak ábrázolása
Gyakran nemcsak a legrövidebb utak súlyainak kiszámítására van szükség, hanem maguknak az utaknak a megtalálásához is. Legyen G = (V, E) egy adott grafikon. Minden egyes csúcsra emlékezünk az elődre. A csúcs prekurzora vagy egy másik csúcs vagy NIL. Az algoritmusok, az elődök lánca befejezésekor. kezdve tetszőleges csúcsponttal v. lesz a legrövidebb út az s-tól v-ig. így ha ≠ NIL, akkor a nyomtatási útvonal (G, s, v) kinyomtatja a legrövidebb utat s-ről v-re.
Az algoritmusok működésének befejezése előtt a π. nem feltétlenül a legrövidebb utakat, de a Gπ = (Vπ, E π) elsőbbségi orientált részgrafikáját tekinthetjük meg. az alábbiak szerint definiáljuk: a Gπ csúcsok azok a G csúcsok, amelyekben az előd nem különbözik a NIL-től, plusz az eredeti csúcs: Vπ = [v] ≠ NIL> s>. A Gπ élek a π [v] ≠ NIL-tól a v felé mutató nyilak. Eπ = [v], v) E. vVπ \ s >>.
A legrövidebb útvonalak fája, melynek gyökere van s egy orientált G'= (V ', E') szubgráf.
ahol V 'V és E' E. amelyek esetében:- V 'a csúcsoktól elérhető csúcsok halmaza.
- G 'egy gyökéres fa.
- minden vV esetében a görbe G-től az s-tól v-ig terjedő út a legrövidebb út a s-tól v-ig a G. gráfban.
Ez az oldal az uCoz-val készült