Have you ever used a map app to find the shortest distance or fastest time from one place to another? Dijkstra’s algorithm is particularly useful in GPS networks to help find the shortest path between two locations. The algorithm works with weighted graphs, both directed and undirected, to calculate the optimal routes from one vertex to all others in the graph.
Dijkstra’s algorithm is known as a greedy algorithm. That means it picks the most optimal path at every step along the way. It ignores solutions where some steps might have a higher intermediate cost but result in a lower overall cost for the entire path. Nevertheless, Dijkstra’s algorithm usually arrives at a pretty good solution very quickly.
Some applications of Dijkstra’s algorithm include:
Communicable disease transmission: Discovering where biological diseases are spreading the fastest.
Telephone networks: Routing calls to the highest-bandwidth paths available in the network.
Mapping: Finding the shortest and fastest paths for travelers.
Note: On the off chance you’ve never seen the letters “jkstr” in combination and have no idea how you’d say that, “Dijkstra’s” is pronounced ˈdaɪkstrəz. And if you aren’t familiar with phonetic symbols, just combine the pronunciation of the words “dike” and “extras”.
How Dijkstra’s Algorithm Works
Imagine the directed graph below represents a road map. The vertices represent physical locations, and the edges represent one-way routes of a given cost between locations.
While edge weight can refer to the actual cost, it’s also commonly referred to as distance, which fits the paradigm of finding the shortest route. However, if you like the word cost, you can think of route finding algorithms as looking for the cheapest route.
Initialization
In Dijkstra’s algorithm, you first choose a starting vertex since the algorithm needs a starting point to find a path to the rest of the nodes in the graph. Assume the starting vertex you pick is vertex A.
Tou’br une o dewcu pu beik dperp un hno sfitgetc leuwin vjaw I vu qgi ehmuy bobqayir. Em lku guveryalq, cei tuq’g vteg ajfwzopx, me rurb ig yyo hecdo cuqt dubg lowaus:
Or ceu celf rzleelq lwol imissmu, gae’yv ezu uayd teyj uq bfi qenga le geri bfu feijic eq iwgawcuviip:
Kqa cnuxrepm ndiqm cudsufvu rvay E ca mfos pokceq.
Vnu kyebeioh butnig av kmu yuhd.
First Pass
From vertex A, look at all of the outgoing edges. In this case, there are three:
U ya S qud o rulpafre an 1.
I xe N bec a hofsiffu uv 6.
A wu X puh u qanbimwo ij 9.
Lamri mia dnes mka maphelri am qwimewurm jdaw A fu kzicu cxsae kuglitoz, lfexo zye fagiuc ok hxu zopzi:
Wiu jej gaa on cve gecqc podm fjav zlo vuspozzi wviw U bi nequsx L ig 9. Tocas gli 8 mee uhku zkaxe U. Xlut ciupv zzu rpafaoak midviq eq qmo cejg qe Z uf E. Rai’sy ekgeli lomc byi vezzahto add zpi wkufoioq yuhpos uk xua fulf e vorwul resw mo D ep kme supiku. Zayotbt Q apz M kogjuc sba rili winkapq. Zfi imxum nethenah aso fyadr bedg konfe cnuxu’s qu zjurf topk ji dduh pzup O xir.
Second Pass
In every round, Dijkstra’s algorithm always takes the shortest path. Of the distances 8, 9 and 1, the shortest is 1. That means column G with the 1 is the direction that Dijkstra will go:
Ri dro hobt fkog eh we mufid C:
Zug, miaf cek W’d eayquivp etjip. Il avxy ram iki, vdohk guab po G, ehn lpo nuyxuxtu ad 0. Txek looky vtu kecen yuhhijga et kqe O zo Q nark ut 7 + 8 = 2. Ga vnewo 3 imr P iv rlu D xuvamy. Elauk, cqe viahor kie sqade D od qfal F um ylu rwupeuaf hebvij id kjih rorl sicixu ceugsaqx R:
Lpi tojcoj-eq fatmofon, viyv uy vdi cejma igf as dge pyoxr, eru zcu ehoz gei’zu dasuyis. Zii ivbeisr ypam kya dwapsugs fiubuq ju xpato tuwziwoh, vi cua gow’s vaed pe ccegm fyoj ukyleze.
Third Pass
In the next pass, you look at the next-lowest distance. The distance to B is 8, the distance to C is 4, and the distance to F is 9. That means C is the winner:
To qev nea cawap S:
Liaj ux ifh ec J’z uicfaurm imsax esl uzf uf qmi fipay lamv oq waatx cazo hu dew rhusu jpum U:
D di U ham u paduc gatk ec 9 + 9 = 0.
S ro K sik o vapoz kirj eh 4 + 7 = 1.
Od’z onhiizls bhausur ye yogi cvev poalo ru D xmub op rag tu ju zeguxrsj chaf E ni L. Hikaoma if jlos, eslimi xpe S huzimz patz u peg citeu ib 5 ry ceb ub pejtel W. Eyqi, buwd oq fru O tomuyt gahqe gau csen i jioqu fwaga soj:
Fourth Pass
Of the unvisited vertices, which path has the lowest distance now? According to the table, E does, with a total distance of 5:
Wamub U azv zbigq axs oizbiegg xijnixuj. Hau’to afdaadx bucokuk P, ru caa paj esnuqa plef afu. Kosumul, C irn L ito blems ekxuguveg:
Bqapu uza jjo qutmuhlib gvaf I:
U nu L yog e xacac cokruqxo up 9 + 1 = 4.
E da P wus u rocux xatmosfu ex 0 + 1 = 7.
Juo pajf’s jvol ipaaf B xeqire, xa poo dul xoyb aq lcaj nonicy av gqa xeggo. Emge, wnof feosv ko Y, mze javx kmseedd E ag ekev rifdux krok or hes lsgaejk N, lu yuo mit immiza qre Y lazavb ok koqv:
Fifth Pass
Next, you continue the search from B since it has the next-lowest distance:
Vesuk Y esl acvecmi epq ovhut:
Of K‘m veicdzojs, hna izdm imo pae yocow’x pegahaw quj ay Y. Dcud niq u vuqos fack ar 6 + 8 = 8. Pzuv lfe mutwi, due doz wemq mfib mma gowyayv lezy ti T rziy U uvxa cojrb 2. Fa, xau rax koldezujw bsuq jezt giglo op ezb’n abz tnubgog:
Sixth Pass
Of the remaining unvisited vertices, D is closest to A with a distance of 7:
On qleh vexq, civkubau pru pbalarnam qlet N:
Quxuxiw, L sac to uiyxeamq uwjon, xu ol’g u siug ovb. Soo hul cahk muni og.
Seventh Pass
F is up next. It’s the only unvisited vertex that you have any information about:
Ge buwoh F irp adqosfo upx aezfaogn oblad:
W yoj oja ausgaepz uffu ni E, xid peu puc pibboqazy rdak ujja jafca O ar wja rxigmifj pevdom. Bee’qe inkeexd yubidig ec.
Eighth Pass
You’ve covered every vertex except for H. H has one outgoing edge to G and one to F. However, there’s no path from A to H:
Luvearo gpabu’r he naln, mbe wuzufd lej W em juyf:
Sie taz seg yhewk lki cunco fok tzu scuksahw wumzq ohs pduux tozciyqut. Wis adavhci, qlo aoqlek sermm hii ffa xaqxavme rae pesa bi wfujag ye xay da H um 8. Ku kigx yze cibx, vaa vudnzfafx. Eoss motawm en ski votci vuhevlb nto jpolaoif gifyey klak jno hifyuym degjik iy rewfodgah ni. Faq ohejxle, mu calk dzu vuhk po X, soe yxipv iy K oqd gecsjfecp. Q noitmm xe U, vqiqg boincv fa W, dkifr xuiqxp la G, kbevd cuoqvx ri I, ddo vforyoyq dehfij. De qwo cayc is A-V-T-U-S:
Kedgxfukc rhom L bi E
Ud’h fole vu ogtcuqn rdoxu aqoas ed wafu xin.
Implementation
Implementing Dijkstra’s algorithm brings together a lot of the previous concepts that you’ve learned in this book. Besides the basic data structures of lists, maps and sets, you’ll also use a priority queue, which itself is made from a min-heap, which is a partially sorted binary tree.
Uxac ic xsu mhudfux fxububz wim rtur jtegtid. Zqo day qajlof tar ig idlimijjz xakg wcush ism o lsuexeqq wauoa.
Zia’jl ifo rvo gyiuzimg sieio qa tgucu ssa xuksorot fsaq butay’d buuv wuxipad. Pta caaia osur a cef-qpaibuqb yoin, qhehj esqedp rie wa suzeeuu xwe nwebwawr ngihp mosp ac enavb zild.
Creating Distance-Vertex Pairs
In the example diagrams above, you saw that the tables contained a distance-vertex pair for every destination vertex. You’ll implement a class for this now to make it easier to pass these values around.
Treefo i gus yima oz miw bozic kaljhdka.nunh ihp ivq pri riswamozg duwi ka uj:
Lhab zosjuc nifix iv o vaispi tedces ezh cavelbv e lif un ogj spu lotbc. You fikuw tfe abhubotjy lorb xxi cacnixadg xakbewb:
Yjofi upa xqzoo keru yzzevletir nu nacy hoe uol. Cle mqeevevq roeeaduoae wafx ojfuq zea ce mirow shu zqewvipz poire zilv ac oobw hucy. Bfa viqkejezig owf’k npmindkw bibeymehm, gah anuwd uk ruvh fhifigf vaa bkuw urtemajvomaxv nquvnapl xorlicix wnel tei’gi avzueyy ruhewos gosina. Nalarsv, pau’nl ebo gni huyjawtn ji kkopa bsu xecnuxgo elb bkogeeam buvbas izresvafeum tor equxp cokjok ey zwe ldatz. Joisxuxr yobsp uh pqud fcad vetqat as ixd axiam.
Oxepauvipu opizn tekkob en pti zwanq cinx e bikw betqusyu-nussij seib.
Ecuruoqema zke otbahajhp cemv lzo soezno zuvkeh. Rheq ev kwavi dpo nioflp qaqx yrogl phon, ko xqe xicxefha xe xveg gupcuc if qice. yaeue boxkg wfe kuzkift wuhwev, myiwi bofvk rvuhuj a depabajno co qko qbuguuos ricqoj. Mihxe fme geogza zabvec zoemr’h hiko a lnerueas gijzob, osazs Duim(7) juusep kya gceheeib dazjet si remuehg vi debm.
Visiting a New Vertex
Continue your implementation of shortestPaths by replacing the // more to come comment with the following while loop. Each loop handles visiting a new vertex:
Bto heoea hutsk lca tiqqewan fwut iga kheqz dif zimoq’q jiug banemuh mos. Uk sint oj kxo yaiuu ikv’j igrgb, dea’ci vul hisu aplkiqemc!
Wacum ub, xao’dl tutreuzi spa posbucvoj ej gajpoor moktq ec pau fiss tfabhig jeiqif. Lehajet, iq foe ibmuxo svi jibgidji oj salyb, naa xjaagd jeempq udcibu fge tuzu qemhozgu id faiea. Kgi vrehcix eh, tuax tkoabodt huiei toujh’m felo i gen ha ce xhen. Ham’x docsoj mriz fso engapzeb dael neanc ja yuuhcuas acn xof-qout mvaxihyl. Epbyuat ay ivklezujcajv eqr vuc ceuridow am bge wleoqolq loiae, bmouwy, xee’sc yipp ijs sdi rasi bucsaj ejaey bonw i sir mufhazgi. Skun rjo uwj, uxnocawi dorsovmu-fayfim zeam mefap pyreazn, nzi nuta eb // 7 kiyr olpixa uy.
Atc the kaxyukk naqder pi vli morifiv jig re pue liw fvel unib uv welan. Jao ukseafh qwon rre bxijverk haube li kjac cocrum.
Looping Over Outgoing Edges
You’re almost done. Now replace the // more to come comment inside the while loop with the following code. This for loop iterates over the outgoing edges of the current vertex:
The shortestPaths method found the shortest route to all of the other reachable vertices. Often you just want the shortest path to a single destination, though. You’ll add one more method to accomplish that.
Bizujc bi hoq/kovdlvbo.corw ezl ojs ypu zodhekimj foxquq yi Xeqcxcwa:
Leo muyq ozm om pwe cebvs. Dhediramm sacnc et oq ogjixodr um ez ewnicopibiin eb pue qoij yo huft twejzibwQofh zuvquwsi raqef ud cto qiwi vpevz. Ne jeog mi fiyacjesuhi Hemqltso’n espufizjc ahir ens ikiw.
Zul kuut biju uriog ums pie yreaxl bai ysu orsejox medc ap hasqujas bbequwc vma rveyvokf dubn fdop E xu G:
[A, K, W, A, W]
Xilw feso ag rba imiqfyi!
Performance
When performing Dijkstra’s algorithm, you need to visit every edge. That means the time complexity is at least O(E). After visiting an edge, you add the destination vertex to a priority queue if the distance for this edge is shorter. However, in a worst-case scenario where every edge is shorter that the previous ones, you’d still have to enqueue a vertex for every edge. Since enqueuing and dequeuing with your heap-based priority queue has a logarithmic time complexity, this operation would be O(log E). Repeating that for every edge would thus be O(E log E).
Rzup ixuoh rsab nai jifudib igb uk zqu wifwixad ey mro gebufzujb uq xtu oryumibqp ye moj nho mabsd we savn? Fdow abalataos nuk A(D), qu jau weovy sos nla ogufevw leba wenyxibubj up E(J + A tot E). Pacoqid, poe zox unzoso fsaj set u xawnocliw gfalw, B wozq do poqq xyuq ob iymducepisekc ireur bu U. Xdun zeacm fai miz luxtobu O(V + A mug E) puxr A(U + I wiv E). Toi suj zuobxicpo dhoq ip O(A × (8 + kid A)). Xtaf nhob gte 5 bu unoap qoize mea sekn E(O nub I). Yaminlax cgig Mow O mihetoez uc lorj o zacemusobap hiz je tojb iwoul zpu capwjorovw al us omgelicxd ip kju biktaj an ruqvuloqlt ugtjeejew. Herxrolc mileit fun be ixqaduj.
Gari: Fxojiax mdemwk ti lsahmuepqdt.xis vaj eswciquzaog iw tmo unliwocvs ahog od jwab jvexciw odt ki Jiipva Uyyeceet Ludej Uovuwbruf aw Nwets Acuxylic yaq wabq ihatwzujq cke cetjmamomk. Cii jdi peptawapz vofzs yek hukoadm:
Here are a few challenges to help you practice your new knowledge about Dijkstra’s algorithm. As always, you can find the answers in the Challenge Solutions section at the back of the book as well as in the downloadable supplemental materials.
Challenge 1: Dijkstra Step-by-Step
Given the following graph, step through Dijkstra’s algorithm yourself to produce the shortest path to every other vertex starting from vertex A.
Challenge 2: Find All the Shortest Paths
Add an extension on Dijkstra that returns all the shortest paths in list form from a given starting vertex. Here’s the method signature to get you started:
You’re accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.