# Dijkstrov algoritem

### Iz Wikipedije, proste enciklopedije

Dijkstrov algoritem ali drevo najkrajših poti se uporablja za iskanje drevesa najkrajših poti. Dijkstra je razvil algoritem za drevo najkrajših poti z požrešno metodo. Drevo najkrajših poti gradimo korak za korakom. Naj bo T množica povezav, ki so že v drevesu. V drevo sprejmem novo povezavo e = (v,u) ∈ E in sicer tako, da naredim unijo T ∪ {e}. Da bo ta unija T ∪ {e} tudi drevo, mora biti natanko eno vozlišče, v ali u, že v drevesu T.

Predpostavimo, da je vozlišče v že v drevesu. Povezavo e = (v,u) lahko sprejmemo, če najkrajša pot od začetnega vozlišča do vozlišča u sme teči le po povezavah, ki so že v drevesu. Torej ne sme obstajati vozlišče w, ki ni v drevesu, takšno, da je pot iz izvora preko w do u krajša krajša kot po povezavah, ki že v drevesu. Da je pot od izvornega vozlišča do vozlišča u preko vozlišč, ki so v drevesu krajša, pa mora veljati, da so vsa vozlišča w (to so vozlišča, ki niso v drevesu) kvečjemu bolj oddaljena od izvora, kot je vozlišče u.

Pri drevesu najkrajših poti imamo usmerjen graf.

## [uredi] Zahtevnost

Časovna zahtevnost algoritma je Θ(n2), ker mora algoritem preveriti vsako povezavo najmanj 1. krat, teh povezav pa je v grafu z n vozlišči n*(n-1) saj gre za polni graf.

## [uredi] Splošna procedura

    1. V drevesu T še ni nobenega vozlišča, zato je podatek oče[i] za vsa vozlišča enak 0.
    2. V drevo T dodam začetno vozlišče.
       oče[začetno vozlišče] = 0
       razdalja[začetno_vozlišče] = 0, torej razdalja od začetnega do začetnega vozlišča je 0
       zadnje vstavljeno vozlišče je začetno vozlišče
    3. Pojdi čez vse vozlišča, ki še niso v drevesu, torej skozi vsa vozlišča razen začetnega vozlišča in določi vozlišče,
       ki je najbližje začetnemu vozlišču direktno in ga vključi v rešitev in sicer:
       oče[u] = začetno vozlišče
       zadnje vstavljeno vozlišče je u
       osvežim razdalje
       Za tista vozlišča, ki še niso v drevesu, določimo razdaljo do začetnega vozlišča tako,
       da vzamemo minimum med razdaljo na prejšnjem koraku, izračunano razdaljo od tega vozlišča
       preko vozlišč, ki so že v drevesu ter razdaljo med začetnim vozliščem in vozlišči,
       ki so v listih drevesa n. Jim prištejemo še pot iz vozlišča, ki je list, do trenutno obravnavanega vozlišča.
    4. Ponavljaj tretji korak, dokler niso vsa vozlišča v drevesu

## [uredi] Zunanje povezave

- Animacija Dijkstrovega algoritma
- Java Applet, ki koračno prikazuje Dijkstrov algoritem
- Dijkstrov algoritem
- Interaktivna stran, ki prikazuje Dijkstrov algoritem

Vzpostavljeno iz »http://sl.wikipedia.org../../../d/i/j/Dijkstrov_algoritem.html«

Kategorija: Algoritmi

##### Views

- Članek
- Pogovor
- Trenutna redakcija

##### občestvo

- Portal občestva
- Pod lipo
- Stik z nami

##### podpora

- Pomoč
- Denarni prispevki

##### Iskanje

##### V drugih jezikih

- Български
- Česky
- Deutsch
- English
- Español
- Suomi
- Français
- עברית
- Bahasa Indonesia
- Italiano
- 日本語
- 한국어
- Lietuvių
- Nederlands
- ‪Norsk (bokmål)‬
- Polski
- Português
- Русский
- Српски / Srpski
- Svenska
- Українська
- Tiếng Việt
- 中文