Új szócikk írása

Szöveg:

<p class="MsoNormal">- adott egy összefüggő G = (V,E) gráf és egy kitüntetett s pontja<br />- a legrövidebb út megkeresésére különböző eljárások vannak: </p><p class="MsoNormal"><strong><font size="4">I.)</font></strong>    - ha az élek száma adja az út hosszát, azaz az élek nem súlyozottak, a <u>szélességi keresést (BFS)</u> kell alkalmazni</p><p class="MsoNormal">        - a szélességi bejárás lényege, hogy a kezdőpontból először elmegyünk annak összes szomszédjába, majd az első szomszéd összes olyan szomszédjába, ahol még nem jártunk</p><p class="MsoNormal">        - ha az összes szomszédot bejártuk, elmegyünk abba a pontba, ahol a legrégebben jártunk, és szomszédain folytatjuk a bejárást</p><p class="MsoNormal">        - mindezt addig folytatjuk, ameddig tudjuk</p><p class="MsoNormal">       - ha s és t  közti legrövidebb utat keressük, a kiválasztott t ponthoz meghatározzuk a q(t) = u₁ pontot; ha u₁nem egyenlő s, akkor a q(u₁) = u₂ pontot, és így tovább, amíg u_k= s lesz, és akkor az s-ből t-be vezető legrövidebb út az (s = u_k, u_k-1, u_k-2, …, u₁,t) lesz</p><p class="MsoNormal">        - a bejárás lépésszáma (e+v)-vel arányos, utána még annyi lépés kell, amilyen hosszú a keresett út</p><p class="MsoNormal"> </p><p class="MsoNormal"><font size="4"><strong>II.)</strong></font>   - az élek különböző hosszúságú utakat modelleznek, azaz súlyozottak</p><p class="MsoNormal">        - ha bejárjuk a gráfot, az u pontra d(u) értéke azt fogja jelenteni, hogy az algoritmus során eddig talált, az s kezdőpontból u-ba vezető utak közül a legrövidebb hossza d(u)</p><p class="MsoNormal">        - a <u>Dijkstra algoritmus</u> akkor használható, ha minden él hossza nemnegatív</p><p class="MsoNormal">        - az algoritmus kulcslépése a következő helyettesítés: </p><p class="MsoNormal"> ha x-ből vezet egy e él y-ba és d(y)>d(x)+l(e), akkor d(y) <span style="font-family: symbol">¬</span> d(x)+l(e)</p><p class="MsoNormal">        - a Dijkstra algoritmus szerint minden él mentén a javítást csak egyszer kell elvégezni, ha már biztosak vagyunk abban, hogy az e él kezdőpontjának d értéke utána már nem fog tovább csökkenni</p><p class="MsoNormal">   0. lépés: S <span style="font-family: symbol">¬</span> {s}, T <span style="font-family: symbol">¬</span> V-{s} és d(s) <span style="font-family: symbol">¬</span> 0 és minden u <span style="font-family: symbol">¹</span> s-re d(u) <span style="font-family: symbol">¬</span> <span style="font-family: symbol">¥<br /></span>   1. lépés: javítás u₀-ból a T-beli pontokba vezető e élekre<br />   2. lépés: T- beli pontok közül legyen u₀ az, amelyiken a d(u) érték a legkisebb, tegyük át u₀-t T-ből S-be<br />   3. lépés: ha T üres, STOP, különben újra az 1. lépéstől</p><p class="MsoNormal">   - az algoritmus lépésszáma legfeljebb v²-tel arányos</p><p class="MsoNormal"> </p><p class="MsoNormal"><strong><font size="4">III.)</font></strong>  - ha olyan irányított gráfot tekintünk, melyben az élhosszak között lehetnek negatív számok, de bármely irányított kör mentén az élhosszak összege nemnegatív kell, hogy legyen, <u>Ford algoritmus</u>át használjuk a legrövidebb út keresésére</p><p class="MsoNormal">            0. lépés: számozzuk meg az éleket 1-től e-ig, legyen i <span style="font-family: symbol">¬</span> 1, és d(s) <span style="font-family: symbol">¬</span> 0 és minden u<span style="font-family: symbol">¹</span>s-re d(u) <span style="font-family: symbol">¬</span> <span style="font-family: symbol">¥</span></p><p class="MsoNormal">            1. lépés: a rögzített sorrendben végezzük el a Dijkstra algoritmusnál említett javítást minden élen</p><p class="MsoNormal">            2. lépés: i <span style="font-family: symbol">¬</span> i+1, ha i>v, akkor STOP, különben újra az 1. lépéstől</p><p class="MsoNormal">        - az algoritmus lépésszáma ev-vel arányos</p><p class="MsoNormal"> </p><p class="MsoNormal"><strong><font size="4">IV.)</font></strong>  - a <u>Floyd algoritmus</u>sal az összes pontpár távolsága meghatározható, ehhez egy olyan súlyozott gráf kell, melyben nincs negatív összsúlyú irányított kör</p><p class="MsoNormal">  0. lépés: minden i, j rendezett párra legyen d⁽¹⁾(i, j) <span style="font-family: symbol">¬</span> l(i, j), továbbá k <span style="font-family: symbol">¬</span> 2</p><p class="MsoNormal">  1. lépés: minden i, j rendezett párra d^(k)(i, j) <span style="font-family: symbol">¬</span> min {d^(k-1)(i, j), d^(k-1)(i, k)+ d^(k-1)(k, j)}</p><p><font size="3"><span style="font-size: 10pt; font-family: times new roman">    2. lépés: ha k=n, akkor STOP, ellenben k </span><span style="font-size: 10pt; font-family: symbol">¬</span><span style="font-size: 10pt; font-family: times new roman"> k+1, és újra az 1. lépés</span></font></p>

Neved: