b'\n_START_ARTICLE_\nDijkstrov algoritem\n_START_PARAGRAPH_\nDijkstrov algoritem ali drevo najkraj\xc5\xa1ih poti se uporablja za iskanje drevesa najkraj\xc5\xa1ih poti. Dijkstra je razvil algoritem za drevo najkraj\xc5\xa1ih poti s po\xc5\xbere\xc5\xa1no metodo. Drevo najkraj\xc5\xa1ih poti gradimo korak za korakom. Naj bo T mno\xc5\xbeica povezav, ki so \xc5\xbee v drevesu. V drevo sprejmem novo povezavo e = (v,u) \xe2\x88\x88 E in sicer tako, da naredim unijo T \xe2\x88\xaa {e}. Da bo ta unija T \xe2\x88\xaa {e} tudi drevo, mora biti natanko ena to\xc4\x8dka (vozli\xc5\xa1\xc4\x8de), v ali u, \xc5\xbee v drevesu T._NEWLINE_Predpostavimo, da je to\xc4\x8dka v \xc5\xbee v drevesu. Povezavo e = (v,u) lahko sprejmemo, \xc4\x8de najkraj\xc5\xa1a pot od za\xc4\x8detne to\xc4\x8dke do to\xc4\x8dke u sme te\xc4\x8di le po povezavah, ki so \xc5\xbee v drevesu. Torej ne sme obstajati to\xc4\x8dka w, ki ni v drevesu, tak\xc5\xa1no, da je pot iz izvora preko w do u kraj\xc5\xa1a kraj\xc5\xa1a kot po povezavah, ki so \xc5\xbee v drevesu. Da je pot od izvorne to\xc4\x8dke do to\xc4\x8dke u preko to\xc4\x8dk, ki so v drevesu kraj\xc5\xa1a, pa mora veljati, da so vse to\xc4\x8dke w (to so to\xc4\x8dke, ki niso v drevesu) kve\xc4\x8djemu bolj oddaljena od izvora, kot je to\xc4\x8dka u._NEWLINE_Pri drevesu najkraj\xc5\xa1ih poti imamo usmerjeni graf.\n_START_SECTION_\nZahtevnost\n_START_PARAGRAPH_\n\xc4\x8casovna zahtevnost algoritma je \xce\x98(n\xc2\xb2), ker mora algoritem preveriti vsako povezavo najmanj enkrat, teh povezav pa je v grafu z n to\xc4\x8dkami n*(n-1) saj gre za polni graf.\n_START_SECTION_\nSplo\xc5\xa1na procedura\n_START_PARAGRAPH_\n1. V drevesu T \xc5\xa1e ni nobene to\xc4\x8dke, zato je podatek o\xc4\x8de[i] za vse to\xc4\x8dke enak 0._NEWLINE_2. V drevo T dodam za\xc4\x8detno to\xc4\x8dko._NEWLINE_   o\xc4\x8de[za\xc4\x8detna to\xc4\x8dka] = 0_NEWLINE_   razdalja[za\xc4\x8detna_to\xc4\x8dka] = 0, torej razdalja od za\xc4\x8detne do za\xc4\x8detne to\xc4\x8dke je 0_NEWLINE_   zadnje vstavljena to\xc4\x8dka je za\xc4\x8detna to\xc4\x8dka_NEWLINE_3. Pojdi \xc4\x8dez vse to\xc4\x8dke, ki \xc5\xa1e niso v drevesu, torej skozi vse to\xc4\x8dke razen za\xc4\x8detne to\xc4\x8dke in dolo\xc4\x8di to\xc4\x8dko, _NEWLINE_   ki je najbli\xc5\xbeje za\xc4\x8detni to\xc4\x8dki neposredno in jo vklju\xc4\x8di v re\xc5\xa1itev in sicer:_NEWLINE_   o\xc4\x8de[u] = za\xc4\x8detna to\xc4\x8dka_NEWLINE_   zadnje vstavljena to\xc4\x8dka je u_NEWLINE_   osve\xc5\xbeim razdalje_NEWLINE_   Za tiste to\xc4\x8dke, ki \xc5\xa1e niso v drevesu, dolo\xc4\x8dimo razdaljo do za\xc4\x8detne to\xc4\x8dke tako, _NEWLINE_   da vzamemo minimum med razdaljo na prej\xc5\xa1njem koraku, izra\xc4\x8dunano razdaljo od te to\xc4\x8dke_NEWLINE_   preko to\xc4\x8dk, ki so \xc5\xbee v drevesu ter razdaljo med za\xc4\x8detno to\xc4\x8dko in to\xc4\x8dkami, _NEWLINE_   ki so v listih drevesa n. Jim pri\xc5\xa1tejemo \xc5\xa1e pot iz to\xc4\x8dke, ki je list, do trenutno obravnavane to\xc4\x8dke._NEWLINE_4. Ponavljaj tretji korak, dokler niso vse to\xc4\x8dke v drevesu'