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
FeladatokSzé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
|