Dijkstra algoritam ("Dijkstra's Shortest Path Algorithm")

[svebee]

Ima li negdje kvalitetno hrvatsko objašnjenje (neka knjiga ili nešto) ili se moram osloniti na (za ovu tematiku težu) englesku literaturu?

hvala

[Bubba]

Covjek je imao vise "algoritama", sto onih u teoriji grafova, pa do onih za prebacivanje u postfix notacije... Koji algoritam tebe tocno zanima?

[svebee]

Autor Bubba

Covjek je imao vise "algoritama", sto onih u teoriji grafova, pa do onih za prebacivanje u postfix notacije... Koji algoritam tebe tocno zanima?

zaboravio dodati - "Dijkstra's Shortest Path Algorithm" - najkraći put između dvije točke.

[Milentije]

http://www.megaupload.com/?d=GWVT44TR

Slajdovi 73-78. Ako budes imao kakvih pitanja javi mi se na MSN.

EDIT: Uglavnom. Posjetiš prvi čvor, poslije njega posjetiš njemu najbliži čvor. Zatim provjeravaš koji ti je nabliži čvor dostižan direktno preko prvog čvora ili preko prvog i drugo. Onda posjetiš taj najbliži čvor, pa opet gledaš koji ti je najbliži čvor koji možeš posjetiti preko dosad posjećenih čvorova. I tako dok ne obiđeš čitav graf.

Nije dozvoljeno ponavljanje iste grane u jednom prolazu kroz graf.

[Bubba]

Autor svebee

zaboravio dodati - "Dijkstra's Shortest Path Algorithm" - najkraći put između dvije točke.

Skokni do knjiznice po Veljanovu Diskretnu matematiku i kombinatoriku, pa pogledaj sto se nudi pod teorijom grafova. Takodjer, baci oko i na Nakicevu skriptu, u kojoj doduse imas Kruskalov/Primov algoritam, ali se oni vrlo malo razlikuju od Dijkstre.

HTH.

[svebee]

Sutra ću probati nešto skužiti s mentorom (inače sam program prijavio kao maturalni rad) ima gotov kod u PHPu, C/C++ itd. tako da to nije problem, ali moram razumijeti algoritam kako bih ga mogao prilagoditi svojim potrebama.

ali koliko sam čitao okolo, vidim da se može prilagoditi za javni prijevoz tj. rutiranje od stanice A do stanice B (ili modifikacije istog algoritma).

ja sam to zamislio da "težine" između svake točke bude neki broj proračunat iz (npr)
1) udaljenosti između stanica
2) ista linija ili ne
3) presjedanje na istoj stanici ili hodanje "preko ceste"
4) vrijeme polaska iduće linije u slučaju presjedanja
5) approx. vrijeme između navedene dvije točke/stanice
6) vrsta prijevoznog sredstva (autobus/tramvaj/metro/vlak...)
7) ...

jel bi to...klimalo?

[rodney]

Autor svebee

ja sam to zamislio da "težine" između svake točke bude neki broj proračunat iz (npr)
1) udaljenosti između stanica
2) ista linija ili ne
3) presjedanje na istoj stanici ili hodanje "preko ceste"
4) vrijeme polaska iduće linije u slučaju presjedanja
5) approx. vrijeme između navedene dvije točke/stanice
6) vrsta prijevoznog sredstva (autobus/tramvaj/metro/vlak...)
7) ...

jel bi to...klimalo?

po meni, jedina bitna stavka za javni prijevoz je vrijeme puta iz cvora a u cvor b.. nebitno je kojim putem ili prijevoznim sredstvom ides, pa neces ic busom zato sto bus ide blizim putem, ako npr. tramvajem stignes pola sata brze. znaci za tezinsku fj-u uzmes vrijeme, a za shvatit algoritam, nadji pseudokod, i pjeske nadji put na par grafova, i razumjet ces kako sto i zasto.

[svebee]

Autor rodney

po meni, jedina bitna stavka za javni prijevoz je vrijeme puta iz cvora a u cvor b.. nebitno je kojim putem ili prijevoznim sredstvom ides, pa neces ic busom zato sto bus ide blizim putem, ako npr. tramvajem stignes pola sata brze.

ali moram uključiti presjedanja u tu priču jer npr. trebam doći od STANICE 1 do STANICE 10. Na pola puta od STANICE 5 - STANICE 6 imam 3min. vožnje istom linijom (istim prijevoznim sredstvom, npr. busom), ali imam i od STANICE 5 - STANICE 6 opciju 1min. tramvajem. Nakon toga opet moram nastaviti prvotnom linijom (jer ona samo vozi dalje). Ako bi se orijentirao na vrijeme (uzmimo da idealno kada izađem iz autobusa kreće tramvaj), tada bih trebao uzeti tramvaj (1<3min.), međutim, nije li praktičnije i dalje biti na autobusnoj liniji unatoč te 2 min.?

[rodney]

Autor svebee

...

pa ako od stanice 5 do stanice 6 mozes ic i busem i tramvajem, to bi se se reklo da ima dvije veze izmedju cvorova 5 i 6, s tim da je vrijeme tj tezina za bus 3min, a za tramvaj 1 + koliko moras cekat, a algoritam bira najkraci put, pa bi trebao izabrat bus. u biti sve one stavke sto si nabrojao (ista linija, presjedanje, hodanje preko ceste) se mogu izraziti pomocu vremena koje je potrebno za te radnje, i pozbrajas ih.

[svebee]

Autor rodney

u biti sve one stavke sto si nabrojao (ista linija, presjedanje, hodanje preko ceste) se mogu izraziti pomocu vremena koje je potrebno za te radnje, i pozbrajas ih.

istina

Autor rodney

...a za tramvaj 1 + koliko moras cekat...

samo ovaj dio, to bi značilo da bi svaki put pri računanju rute od točke A do točke B trebao za svako moguće presjedanje (te općenito računanje vremena) morao dinamički računati vrijeme tj. težinu puta (izuzev onih puteva gdje nema promjena tipa stanica 1 do stanice 2 uvijek ide samo tramvaj - to bi vrijeme bilo statično (approx. naravno, ali se nebi mijenjalo)) jer bi ono naravno ovisilo o polasku autobusa/tramvaja te dolasku istoga na stanicu.

probat ću složiti pa javim rezultate/brzine

[Milentije]

Da, za svaku granu računaš nezavisnu težinu (težinu koja nema veze sa ostalim granama). Inače, za optimizaciju protoka imaš neke druge algoritme (možeš ih naći u onom PPP što sam ti poslao).

[rodney]

Autor svebee

samo ovaj dio, to bi značilo da bi svaki put pri računanju rute od točke A do točke B trebao za svako moguće presjedanje (te općenito računanje vremena) morao dinamički računati vrijeme tj. težinu puta (izuzev onih puteva gdje nema promjena tipa stanica 1 do stanice 2 uvijek ide samo tramvaj - to bi vrijeme bilo statično (approx. naravno, ali se nebi mijenjalo)) jer bi ono naravno ovisilo o polasku autobusa/tramvaja te dolasku istoga na stanicu.

takva funkcija se naziva "heuristicka evaluacijska funkcija", a jedan od jednostavnijih algoritama koji bi bio dobar za ovaj problem je A*. iako mozes gledat i druge algoritme za usmjereno pretrazivanje (neznam koji se spominju o ppp sto je milentije poslao..).

[svebee]

tnx. vidim da A* ima dio Dijkstrinog algoritma + heuristicki pristup (EDIT: ili on može koristiti i dinamičke težine?)

no, imam jedan problem - koliko sam shvatio, oba algoritma zahtijevaju unaprijed definirane težine između svih vrhova.

ako ja imam 3 rute, ovisno s koje prethodne točke/vrha dolazim ovisit će mi težina između slijedeća dva vrha. što želim reći? ako imam ovu situaciju



zamislimo da linija br. 2 ide ravno do kraja - tada će težina od "središta" do slijedećeg vrha prema kraju biti najmanja (nema presjedanja), ako će pak ispitivati s linije 1 ili 3 - postoji presjedanje i automatski je težina veća, no međutim može li se definirati više težina za isti put (osim naravno smjera tamo/natrag)?

[rodney]

Autor svebee

... no međutim može li se definirati više težina za isti put (osim naravno smjera tamo/natrag)?

ne mozes bas imat vise tezina za isti put, ali, ono sto mozes je imat vise puteva izmedju ista dva cvora. nesto kao:



(ja sam crtao usmjereni graf, mozes isto to i sa neusmjerenim).

vec sam rekao malo vise gore da mozes imat vise veza..

edit:

malo sam razmisljao, i mozda bi ti bilo jednostavnije poigrat se sa grafom, recimo nesto ovako:
.

ako bi tako prezentirao mrezu, onda nemas problema sa dinamickim tezinama ni sa icim drugim, samo pises sve tezine (na ove crvene crte, jelte) i pustis algoritam da se snalazi..

[svebee]

Autor rodney

ako bi tako prezentirao mrezu, onda nemas problema sa dinamickim tezinama ni sa icim drugim, samo pises sve tezine (na ove crvene crte, jelte) i pustis algoritam da se snalazi..

ali problem je što su te težine varijabilne (ovisi s kojom se linijom dolazi na početnu stanicu jednog "ruba"). npr. imamo ovu sitauaciju (napomena: stanica na kojoj se križaju je ista, ista strana ceste, sve isto)



kako da ja algoritmu kažem da ako "dolazi" s donje strane, s plave linije uzima vrijednost 150, a ako "dolazi" s lijeva (s crne linije) uzima vrijednost 10.

to me muči...

[rodney]

Autor svebee

ali problem je što su te težine varijabilne (ovisi s kojom se linijom dolazi na početnu stanicu jednog "ruba").

to bi rjesio da uvedes heuristicku funkcijuju koja racuna do sad prijedjeni put. tezina brida u grafu mora bit jedinstvena. ali....

Autor svebee

kako da ja algoritmu kažem da ako "dolazi" s donje strane, s plave linije uzima vrijednost 150, a ako "dolazi" s lijeva (s crne linije) uzima vrijednost 10.

to me muči...

mozes napravit bolju reprezentaciju rjesenja (citaj bolji graf).
hint:


sad tek vidio, fali mi jos jedna crta, di plavi bus odlazi na iducu stanicu...

[svebee]

nadasve zanimljivo rjesenje neznam zašto sam se ja (nesvjesno) ograničio na to da taj "imagnirani" graf mora odgovarati fizičkom obliku u stvarnosti... uglavnom, shvatio ideju, tnx.

javim se za par dana

Autor Bubba

Skokni do knjiznice po Veljanovu Diskretnu matematiku i kombinatoriku, pa pogledaj sto se nudi pod teorijom grafova.

neznam, ali ono tamo je (po)prilično komplicirano štivo, dok tek nešto skužim trebam ogromnu pomoć...probat ću "easy-way" - bez mat. uvjeta, funkcija i ko zna čega sve ne ako neće ići, e onda ću se baciti na to.

[svebee]

ima li netko ideju kako "unaprijed" izračunati težine rubova?

jer ako imam stanice A,B i C i ako idem direktno A -> C, rubovi (vremena polaska busa na stanicu) će biti drugačiji nego ako se ide A -> B -> C. Kako mogu odrediti rubove "unaprijed" jer ovisno kako se Dijkstra širi - tako se proračunavaju i rubovi tj. ovisno o ruti koju on pospoji - na taj način će se generirati i rubovi.

Kako to izvesti?

[Milentije]

Nisam najbolje shvatio. Mozes li skicirati konkretan slucaj?