Algoritmy řešící bludiště

• Sledování zdí - algoritmus je založený na principu, kdy při vstupu do bludiště se vybere pravá zeď a podél ní se pořád pokračuje. Směr postupu je daný, používá se i při vstupu do křižovatky a je během celého algoritmu neměnný. V implementaci toho algoritmu bylo zvoleno pravidlo pravé ruky, tedy na každé křižovatce se zatáčí doprava.
  
  Výstupem tohoto algoritmu není trasa od vstupního do výstupního bodu bludiště, ale jen zjištění zdali taková trasa existuje. Konkrétní trasu lze na výstup algoritmu dostat například průběžným ukládáním každé navštívené buňky.
  
  
  
  
• Vyplňování slepých konců - algoritmus postupně prochází celé bludiště, a pokud narazí na slepý konec, označí si ho a od něho i celou cestu až k nejbližší křižovatce (vyjme buňky z množiny možných řešení). Takto se postupuje do té doby, než jsou eliminovány všechny slepé konce a na výstupu je jen množina buněk obsahující trasu řešící bludiště. Algoritmus tedy nenachází řešení bludiště jako takové, pouze ho redukuje.
  
  
  
  
• Trémauxův algoritmus - algoritmus prochází bludiště, a na zásobník jsou ukládány buňky cesty (vrcholy grafu) od vstupního bodu bludiště. Na křižovatce se volí směr dalšího postupu náhodně po hraně, která ještě nebyla navštívena. V případě, že cesta končí slepým koncem, algoritmus se vrací zpět k poslední křižovatce a odebírá buňky ze zásobníku. Jakmile se vrátí zpět na křižovatku, označí si slepou cestu jako nesprávnou a opět pokračuje náhodným směrem, dokud nejsou všechny možné směry křižovatky vyčerpány.
  
  
  
  
• Hledání nejkratších cest - algoritmus vychází z podmínky, že hrany grafu jsou stejně dlouhé. Celý graf je potom prozkoumáván postupně ve vlnách. V první vlně se zkoumají vrcholy ve vzdálenosti 1 od vstupního vrcholu, ve druhé vlně vrcholy ve vzdálenosti 2 a tak dále dokud není nalezen cíl. Trasu řešení bludiště potom algoritmus zobrazí zpětným průchodem nejkratší určené cesty.
  
  
  
• Dijkstrův algoritmus - na algoritmus lze pohlížet jako na zobecněný algoritmus prohledávání do šířky. Vlna se ale nešíří na základě počtu hran od zdroje, ale v závislosti na vzdálenosti od zdroje, ve smyslu ceny hran. Vlna proto zpracovává jen ty vrcholy, k nimž již byla nalezena nejkratší cesta.
  
  Vstupem algoritmu jsou ohodnocený graf, počáteční vrchol a cílový vrchol, výstupem pak je nejkratší trasa mezi zadanými vrcholy, nebo zpráva o neexistenci takové trasy.