Dijkstra shortest path algoritmus

Algoritmusok

hello,

A fenti algoritmussal ket pont kozotti utvonalat szepen meg tudom talalni. Viszont, ha van tobb eloirt pont, amit a start es a cel kozott erinteni kell, akkor hogyan fussak neki?

A koztes pontok szama valtozo.

Egy otletre lenne szuksegem, hogy elmozduljak a holtpontrol.

koszi

  • 3991 megtekintés

( Panther v | 2008. 10. 30., cs – 20:24 )

Kezdőpont - köztes pontok egyesével, köztes pontok párban, köztes pontok egyesével és végpont, ez így jópár Dijkstra és jókora overhead, de működik. Van elegánsabb megoldás is, csak az nem jut eszembe :S

Floyd-Warshall-lal O(n^3) időben megvannak a pontpárokra a legrövidebb utak, de a Dijkstra vagy Bellmann-Ford a jobb csak a fent nevezett pontokra a jobb, hiszen ez így az algoritmusra nézve csak konstans szorzót jelent, és nem n-eset. Ezek után csak ki kell választani, hogy melyik az optimális út.

Amit elsőre írtam, az az első gondolat, ha a Dijsktra és tsai "rég voltak". Hm, muszáj lesz ezeket is átnéznem.

"Amit elsőre írtam, az az első gondolat, ha a Dijsktra és tsai "rég voltak". Hm, muszáj lesz ezeket is átnéznem."
Én is erre a következtetésre jutottam... :-(
Most kicsit elővettem a FW-t valóban jó megoldás lehet rá!
----
"A hibás logikájú emberek több bűnt követtek el akaratukon kívül, mint a rossz emberek szándékosan."
Bárcsak...

( nosy | 2008. 10. 30., cs – 21:30 )

udv,
a koztes pontokat csak ugy egyaltalan erinteni kell
vagy az erintes sorrendje is eloirt?

( denes | 2008. 10. 30., cs – 22:24 )

szerintem ez lenyegeben az utazo ugynok problema (amit polinomialis idoben nem sikerult meg senkinek megoldani). Lasd pl. wikipedia

- Use the Source Luke ! -

gondolkozz egy kicsit. veszed azt a par pontot amit erinteni kell, kiszamolod a koztuk levo ut koltseget, osszekotod a pontokat es rairod a kiszamolt koltsegeket az elekre - es ott van az utazo ugynok problema. egy kulonbseggel, hogy nem kell jelen esetben visszaerni a kezdopontba - de ez nem lenyeges, mert ha igy megoldod X ido alatt, akkor vegigprobalgatva minden kezdo es vegponttal megoldhatod X*n^2 ido alatt az utazo ugynok problemat, amibol kovetkezik, hogy X sem fog menni polinomialis ido alatt.

szerk120: persze senki sem mondta, hogy polinomialis ido alatt kell (vagy lehet) megoldani, es en meg nem mondom azt, hogy dijkstra-val vagy akarmi hasonlo algoritmus felhasznalasaval ne lehetne megoldani. csak annyit mondok, hogy ez egy jol ismert problema.

- Use the Source Luke ! -

Nagyon nem. Az utazó ügynök probléma NP nehéz. Ott az jelenti a nehézséget, hogy optimálisnak kell lennie és - most jön a nehéz rész - minden pontot pontosan egyszer kell érinteni.

Itt senkit nem zavar ha az optimális úthoz többször is átmegyünk egy-egy csomóponton, és persze nem is kell feltétlenül mindent bejárnunk.

--
The Net is indeed vast and infinite...
http://gablog.eu

( zamek | 2008. 10. 31., p – 12:04 )

hali,

Van egy mukodokepes megoldas.
A forrasbol kikeresem a hozza legkozelebb eso koztes pontot.
Majd ezt tekintem forrasnak es a fenti lepest ismetlem, amig el nem fogynak a koztes pontok.
A vegen az utolso koztes ponttol keresek utat a celig.

Persze lehet olyan korulmenyeket teremteni, hogy behal az algoritmus:
ha az utolso koztes elemtol nem vezet ut a celig, de egy elozotol igen, akkor bukta van.

Viszont az anyagmozgato technologiaban tesztelve kitunoen mukodik.

koszi,
Zamek