A legrövidebb utakat meghatározó algoritmusok tárgyalását egy speciális esettel kezdjük: egy négyzetrácson mozoghatunk, mindig élszomszédos mezőkre léphetünk, és bizonyos mezők tiltottak ("fal"). Keressük két megadott mező közötti távolságot, lépésekben számolva. Például kérdés lehet, hogy milyen messze van a piros mező a zöld mezőtől:
A választ a
szélességi keresés adja, ami ilyen "térképen" nagyon egyszerűen programozható: a kiinduló mezőre 0-t írunk, a szomszédaira (ahova lehet lépni) 1-et, majd általában ha minden K-t beírtunk, akkor az összes K még be nem járt szomszédaira K+1 kerül. Ha elértük a piros mezőt, akkor az oda írt szám pontosan a keresett távolságot mutatja.
Az algoritmus helyességének belátásához csak azt kell észrevenni, hogy pontosan azok a mezők vannak N távolságra a kiinduló mezőtől (N>1), amelyeknek van olyan szomszédja, amely N-1 távolságra van a starttól. A megvalósításnál arra kell vigyázni, hogy csak akkor kezdjünk K értékeket beírni, amikor már az
összes K-1 távolságra lévő mezőt megjelöltük. Ezt legegyszerűbben a sor adatszerkezet használatával tehetjük meg:
d[START] := 0
Sorba(Start)
Ciklus amíg a Sor nem üres
x := Sorból
Ciklus x jelöletlen y szomszédain
d[y] := d[x]+1
Sorba(y)
Ciklus vége
Ciklus vége
Rekurzív megoldás
Ha nem akarunk Sor-ral dolgozni, egy rekurzív megközelítés is működhet. Azonban az órai elemzések azt mutatták, hogy ez a megoldás nagyon nem hatékony, ha a labirintusban nagy üres termek vannak.
A rekurzív eljárás:
Eljárás bejár(x)
Ciklus x négy lehetséges y szomszédjára
Ha y nem fal és d[y] > d[x]+1 akkor
d[y] := d[x]+1
bejár(y)
Elágazás vége
Ciklus vége
Eljárás vége
A keresés indítása:
d[] := végtelen; d[START] := 0
bejár(START)
2004-2016 BDG algoritmus szakkör