dijkstrov algoritem za iskanje najkrajse poti v usmerjenem grafu izdelala mitja lustrek bostjan keber fakulteta za racunalnistvo in informatiko trzaska ljubljana mentor asist mag rajko mahkovic predstavitev dijkstrov algoritem resi problem iskanja najkrajse poti v usmerjenem grafu g v e pri cemer je v mnozica vozlisc angl vertices e pa mnozica povezav angl edges dolzine vseh povezav pa so nenegativne algoritem gradi vpeto drevo vozlisc tako da izhodiscnemu vozliscu x koren drevesa doda vozlisce ki se ni v drevesu in za katerega velja da ima najkrajso pot od izhodiscnega vozlisca tako doseze da ne obstaja najkrajsa pot do izbranega vozlisca preko nekega vozlisca ki se ni v grafu usmerjen graf slika vpeto drevo najkrajsih poti slika slika prikazuje primer usmerjenega grafa z nenegativnimi razdaljami med vozlisci slika pa iz tega grafa zgrajeno vpeto drevo najkrajsih poti angl shortest path spanning tree opis algoritma v psevdokodi opis v psevdokodi dijkstrov algoritem uporablja pri iskanju vozlisca z najkrajso potjo prioritetno vrsto q vozlisc za katera je znana dolzina vsaj ene poti od zacetnega vozlisca na zacetku izvedemo inicializacijo postavimo zacetne vrednosti parametrov d razdalja med vozliscema na neskoncno in pi prednik na nil v koraku izpraznimo mnozico s v koraku dodamo prioritetni vrsti q vsa vozlisca v iz grafa g korak opisuje glavno zanko ki se izvaja dokler ne dodamo v drevo vseh vozlisc oziroma dokler prioritetna vrsta q ni prazna v zanki brisemo vozlisce z najmanjso prioriteto iz prioritetne vrste q mnozici s pa dodamo trenutno vozlisce u grafa g v prvem izvajanju zanke je u s koren v for zanki vsakemu ze obiskanemu vozliscu popravimo razdaljo in prednika v zadnjem koraku sprostitev u v w naredimo naslednje razdalja med vozliscema v in u je w ce d d w potem d d w in pi u sicer se ne zgodi nic opis delovanja s primerom zacetna situacija slika a kaze situacijo pred prvo iteracijo while zanke senceno vozlisce ima najkrajso razdaljo d in je izbrano kot vozlisce u v vrstici v psevdokodi za koren drevesa velja d s s in pi nil slika b drugo izvajanje while zanke d s u d s x pi u pi x s slika c ker je d s x d s u in d s u d u x d s x d x u izberemo povezavo med vozliscema s in x d s x ker je razdalja d s x d x u d s u izberemo povezavo med vozliscema x in u dolocimo se razdaljo od vozlisca s do y in v preko vozlisca x d s y d s x d x y in d s v s s x d x v slika d izberemo vozlisce y in ugotovimo d s x d x y d y v d s x d x v slika e v naslednji iteracijo najdemo se krajso pot do vozlisca v postavimo se v u in ugotovimo d s x d x u d u v d s x d x y d y v slika f postavimo se v vozlisce v in ugotovimo da smo dobili vpeto drevo z najkrajsimi povezavami casovna zahtevnost kako hiter je dijkstrov algoritem najprej preucimo moznost kjer je prioritetna vrsta q v s vsa vozlisca ki se niso obdelana implementirana s poljem tabelo v tem primeru je vsaka operacija izlocanja najmanjsega elementa iz q extract min q casovne zahtevnosti o v v je stevilo vozlisc v algoritmu se pojavi v teh operacij ker moramo obdelati vsa vozlisca extract min q je torej skupaj casovne zahtevnosti o v vsako vozlisca vstavimo v mnozico s natanko enkrat torej v for zanki pregledamo vsako povezavo seznama adj natanko enkrat v adj so vsa vozlisca sosednja u ce je v grafu e povezav se for zanka izvede natanko e krat vsaka iteracija pa je casovne zahtevnosti o skupna casovna zahtevnost celotnega algoritma je torej o v e o v druga moznost je implementacija prioritetne vrste z dvojisko kopico angl binary heap taksnemu dijkstrovemu algoritmu pravimo tudi prilagojen dijkstrov algoritem angl modified dijkstra algorithm vsaka operacija extract min q je v tem primeru casovne zahtevnosti o log v tudi tu imamo v teh operacij da zgradimo kopico potrebujemo o v casa segment sprosti je sestavljen iz klica funkcije ki zniza prioriteto vozlisca v vrsti decreasekey ki je casovne zahtevnosti o log v teh klicev pa je v najslabsem primeru e skupna casovna zahtevnost je torej o v e log v o e log v mozna je tudi implementacija prioritetne vrste s fibonaccijevo kopico angl fibonacci heap vec o tem je zapisano v poglavje s cimer dosezemo casovno zahtevnost o v log v e amortizirana casovna zahtevnost v extact min q operacij je v tem primeru o log v vsak e decreasekey pa je casovne zahtevnosti le o torej je celotna casovna zahtevnost dijkstrovega algoritma v primerih kjer je vec decreasekey kot extract min ukazov o log v program za demonstracijo dijkstrovega algoritma program za demonstracijo omogoca risanje grafa dodajanje vozlisc in povezav v graficnem nacinu shranjevanje in nalaganje grafa z diska izvedbo dijkstrovega algoritma izvedbo dijkstrovega algoritma po korakih graficno predstavitev najkrajse poti v datoteki dijkstra zip kb ki jo je moc prenesti s tega streznika se poleg demonstracijskega programa za bitno okolje windows nt nahaja se kratko navodilo in datoteka z grafom iz stran literatura cormen introduction to algorithms the mit press cambridge kononenko nacrtovanje algoritmov in podatkovnih struktur zalozba fe in fri ljubljana