Szakkörök‎ > ‎Algoritmus szakkör‎ > ‎2011-2012‎ > ‎

6. óra

2011.10.24.

Továbblépünk a gráfbejárások és legrövidebb utak témakörében. Két elemmel finomítjuk legutóbbi algoritmusunkat:
  • a bejárandó gráf éleit nekünk kell "kiszámolni"
  • a legrövidebb út hossza mellett ki kell írnunk egy lehetséges legrövidebb út "állomásait" is

Feladatok

Szélességi bejárás út megjegyzésével

Az előző órai algoritmus így módosul:

Ciklus minden i csúcsra
    d[i] := -1
    apa[i] := i
Ciklus vége
d[START] := 0
Sorba(Start)
Ciklus amíg a Sor nem üres
    x := Sorból
    Ciklus x bejáratlan y szomszédain
        d[y] := d[x]+1
        Sorba(y)
        apa[y] := x
    Ciklus vége
Ciklus vége


A bejárás végeztével így kapunk egy legrövidebb utat (abban az esetben, ha a CÉL elérhető, vagyis d[CÉL] > -1):

Kiír( c )
    Ha apa[c] <> c akkor Kiir( apa[c] )
    Ki( c )
Eljárás vége