Algoritmus
A falak "szigetek" az aknatengerben, ezek lesznek a gráf csúcsai. Teljes gráfot csinálunk,
súlyozott élekkel. Az élek súlya a falszakaszok közötti távolság (tehát a legrövidebb létrahossz, amivel áthidalható a két "sziget" közötti űr. Ezen a gráfon egy speciális távolságfogalom értelmezhető: két pont közötti úton a leghosszabb él hossza. Ezt kell minimalizálnunk, a megfelelő út megkeresésével. Ez Dijkstra-algoritmus, egyszerű módosítással.
Távolság függvény
Ez volt a nehezebb rész. Sok esetet kell vizsgálni. Két szakasz távolságát kell kiszámolni, ahol a két szakasz vagy párhuzamos, vagy merőleges.
Ha merőlegesek:
Nézzük az egyik szakaszt,
ennek végpontjaiban állítsunk merőlegest egyenesére, így a síkot 3 sávra bontottuk.
Minden sávban három esetet vizsgálunk, aszerint, hogy a másik szakasz az első
"alatt", "felett", vagy vele "metsző" helyzetben van.
Párhuzamos esetben kicsit egyszerűbb a helyzet.
Peregi szabály :) NEM HASZNÁLUNK VERSENYEN LEBEGŐPONTOS ARITMETIKÁT. Mivel a
távolságokat nem kell összegezni, dolgozhatunk a távolságok négyzetével, tehát
hosszú egészekkel.
Módosított Dijkstra-algoritmus
Indiana_dijkstra(G)
minden v csúcsra: létra[v] := végtelen;
létra[indiana] := 0
Q := G
Ciklus amíg nemüres( Q )
u := kivesz_min(Q)
Ciklus u minden v szomszédjára
l2 = max(létra[u], táv(u, v))
Ha l2 < létra[v] akkor létra[v] := l2
Ciklus vége
Ciklus vége
Kódok
