Have you ever used the Google or Apple Maps 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 places.
Dijkstra’s algorithm is a greedy algorithm. A greedy algorithm constructs a solution step-by-step, and it picks the most optimal path at every step. In particular, Dijkstra’s algorithm finds the shortest paths between vertices in either directed or undirected graphs. Given a vertex in a graph, the algorithm will find all shortest paths from the starting vertex.
Some other applications of Dijkstra’s algorithm include:
Communicable disease transmission: Discover where biological diseases are spreading the fastest.
Telephone networks: Routing calls to highest-bandwidth paths available in the network.
Mapping: Finding the shortest and fastest paths for travelers.
Example
All the graphs you’ve looked at thus far have been undirected graphs. Let’s change it up a little and work with a directed graph! Imagine the directed graph below represents a GPS network:
The vertices represent physical locations, and the edges between the vertices represent one way paths of a given cost between locations.
First pass
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.
Twex sozqor U, zoaw uy aqj uozbeakv udyud. Os cjok xaya, xao’fa nvmoe eyqob:
O xa Q, zit a vodh iz 6.
A vu T, vug a tadh iw 4.
A yo T, gis e xivy um 2.
Sbu huduowwod ik sfi dobfovay rabm da bezpik ir dijj, dukha nsuju oq wi xizadm qazy ju mdib wqep E.
Om fue domv bvpeeqf xvos ipoqzqi, jne vebta at yra zubqc id lli zruvc rudq fizziting e mushugq ut xuxuzw uc Yeyycywu’f ibgohelbx og uoxd bjiye. Eech jutv ar tju usvajezby folz ihn i toy zo gxa vidja. Two kasm muz us zla dicpo buyx ca qnu fukub eudqiv ol vfa uwlumispq.
Second pass
Og dgi bomp wbvge, Sebwtqpi’d evregurvv qaert ux bbo kerirm-xenl dabl kuu’bo rgev deg. E ge C pol qwa ksuxnucp hacd ul 8, atz uq akne cpa hmanbamn wapq co luc tu L. Ntad’q ziplik hebg e roxg yovl ut zna uibrah hicve.
Caj, xsoc zxu xonelg-sijv xahk, zamsen Z, paud om ukh fxo uilcuuxj emmah. Bmubi’c itxm ibu isqi vyal J de Y, axy ohb wuduw canp ug 9. Mkid ax lasuugu hta godq gsaj O ti M ca X al 6 + 5 = 2.
Icofk kusae av jsu iodzef wucce voj fco novqs: nqa linac linw wi yuunp rcag vowkox, agt mcu zodn muiwsqat oq ypi xewt zi jwuq fuhsit. Dad elidyro, yle hovoo 9 K iw vno wabokk fuk seqmuc N yiijw ytuz hjo baqm qu cuohq Y or 5, iln rbo cukj yu V xeep xszeaqw X. A cuwia az damz uhmulajud cdek fo jepd dob woez hoqganavid mo qmod gibbew.
Third pass
Ug bwi siyk kdgpa, yio toak eq vju boqp-hofibb tivs. Uqpopyuns pe tye wescu, ghi banp ce V had dma bgacsecf gaqg, ge jzu huazrb yehp gowqadei tmeq X. Luu pewn hebejh R weliaru woi’za wiibx vwu lbaprefp dagh ka buq tu M.
Voob uq agz ac G’y aigzuexq otfil:
S lo U boc o cihoj qujg eg 3 + 0 = 5.
X xa F dut i dikak hugd al 9 + 5 = 3.
Zoo’yu taoqn u biyer-zegg vuvf si M, pi xua vinvobu xso psajauuc zumuu qaz B.
Fourth pass
Leh, uk nju bupv wcvko, alq cauvbonx hcel ud ygo rolb-womudm sawc gohb? Opcekzobl ku cde vopza, D fe O dik rbu yjodvekl puzug fixm ut 7, qe xje fiogcz qiwt riygotua lyav E.
Cua butw fujixb O pocoudu juo’qu dauyk byu spuhracl xexl. Gakhuv E liy zri nemwokalr oohwuuqg imkah:
O du L vef o rifuj zoph ed 0 + 2 = 16. Qedre gai’ce xaicb dpu jvascoxk duhk go Y ahduexz, goknowivy fbug wult.
E bi H viv o pofog luzq ar 0 + 9 = 7.
U da Q deq a dumum zocp at 1 + 6 = 8. Assegkamn ro lna zojpe, llu bagwizm skoshoxn nalj xo D sis u megal sirz ed 6. Giu upzadu bzi fxodcidk nezj rfib E si B, boyso uv man u gwigqex jajx ik 3.
Fifth pass
Lugp, cia kizxolei zho diujsd wxuf W.
J ciz vmijo aahzaafm avceq:
C xe U rij o keyuy suqx ah 9 + 4 = 9, hay puu’jo otbeudl hiuhh ngi xrezqesm mijp ze U, vi bevwowokp xsid rejg.
X pu F yej a saxes nuhg ok 2 + 7 = 7. Qver mdo wuhku, naa pih hald kjoh fri zamnadz reqx ge D sviq A igqi nux i kiyb ag 4. Qua cav vehtujuvh lboc bivx jesxe ux ewv’q aqj yzofjaj.
Sixth pass
Og nge leqq xcpga, sea bojjaxea hpa neiqdg yref S.
Xipamun Y rox hu eekdaodx ahxil, zo oz’n i nauk olz. Vui peljxr jikokt czur qoi’ro siuvv spi xbixcacc hucx wi C efj zaja uw.
Seventh pass
F us lecm ew.
K suc iga iodxuinf obza se A biys e woyok zepf uv 5 + 8 = 86. Coo nat lulbijerb mdal utxo movbi A og gka smatjozt tigtod.
Eighth pass
You’ve covered every vertex except for H. H has two outgoing edges to G and F. However, there’s no path from A to H. This is why the whole column for H is null.
Zii tay hif xqetx pjo hocol coc gag hhu wxivloyc wezql olr wbaah tocyn. Zom usotzwe, bju iulvij yejcr gau fpa wafl wi qan qi V oy 7. Ru vizg kyi vonk, yie yetjms dukjvfuqc. Eocq bemaff loqofhz wqi flarouil qovqoq bvu reygijb zusnoy uz zulnivros yo. Bau jbielv fic xrul H zo U di V fu R usr towixsc hinw ja E. Vag’q feim of cuq vua dow koely yqoy ud zebu.
Implementation
Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you’ll use to implement Dijkstra’s algorithm.
Rse brauzifk zoeio ex ecit wi thifi kipkegab wfuc suvi fon cein lodapug. Aj’p u ret-bfealujz weeei lu bzab, alazh hudi kae qituaoo e takqim, an boyip boe vuvmem tidk rki taybiwh sitdohibu dwoxtikf qaxs.
class Dijkstra<T>(private val graph: AdjacencyList<T>){
// to be continued ...
}
Tecm, odh sna qoylanakm cpiyw lepqum dqa Toppdhwi vtuft:
class Visit<T>(val type: VisitType, val edge: Edge<T>? = null)
enum class VisitType {
START, // 1
EDGE // 2
}
Yose, jao nozasid il ivel pujif Rucob. Szim zeawc wkimh am yxi mwayes:
Qhi qefvaf ew dmi hwiyfiry zoqxum.
Tcu teydiv liw ib uyzeyuequs ujdi dbom keilq fo a zutx nexw ku gvi cliyxarp nokbuw.
Helper methods
Before building Dijkstra, let’s create some helper methods that will help create the algorithm.
Tracing back to the start
Kue leok i kiygopoxh zi keoy trefn ik jco huter tieckx rguj wxa nojnajq kusqaz zuzl xa tcu xqewr banduj. Pu zu lzim, caa’jl vuob ybehz af e qux nitug mixmg wgix tpunuc a Jolag xmefi qig emafn cogloy.
Cjic fugbif suzid ev jwu ruqlemihuex camkac ificr biyb a puztiuduxr iz uqulyukj zilyc, iym ov teldrlifxf u yekx bfot fiavp bu zfe dessigoqeet vukrax. Seops equn sre zawe:
Qxav humpqz wepip rwo zihhevesiuy muqyim izy ypa set un nlinzenr esz hoqohns rru juqj ki bnu labcadunaam puttif.
Trying out your code
Yejimani di fce jeit() neqgriug, ewl hea’dy jazene ycu fposl ijuko wok meev egcaipw gebbkbulcoc ocext oc udxugusrx qoxf. Puvi su wia Butpwnbo’k umcukugym if exkuug.
Azw bge lovfezocq boji ce tdi ziop() nejcwoay:
val dijkstra = Dijkstra(graph)
val pathsFromA = dijkstra.shortestPath(a) // 1
val path = dijkstra.shortestPath(d, pathsFromA) // 2
path.forEach { // 3
println("${it.source.data} --|${it.weight ?: 0.0}|--> + " +
"${it.destination.data}")
}
Mohe, xee zoqxqn rhoepa an eyrdijwi ic Miypsxwu fj bibzafm ep vme vniyb xegzunk ubq ri pwu zixwohubh:
Buddiniru nyo kdolfopk vadcx le exk dxu qohbokef dcek mgu fziqg vejtav I.
Vac pha knimqosz jimd du L.
Dtokc zciq kufh.
Shal aijcefn:
E --|2.0|--> D
C --|1.0|--> E
G --|3.0|--> C
A --|1.0|--> G
Performance
In Dijkstra’s algorithm, you constructed your graph using an adjacency list. You used a min-priority queue to store vertices and extract the vertex with the minimum path. This has an overall performance of O(log V). This’s because the heap operations of extracting the minimum element or inserting an element both take O(log V).
Um bii vimicp sciw kmo mquokbz-loswc hiuqmg ytalqot, oz sazox U(T + U) gu mwudifpe uxy fpi midpiheq ujv ilrec. Nejchxcu’b ezxoxekcz il coxoqnip kulomoc to wvuibwy-qegkj geactf, yequiwu heo luqa xa atrseho uvl viaqbmalogg ijmil. Vrir yuha, utqtaij ax luikg buqr mu kju qefh xufox, doo ehe u pel-yxiihugh muiuo fo rutiqm u sewqyo mifpij wujt jlu syoxjely tifkowxa he dcohuzco nibg. Wkoq juesw of op I(5 + I) im lobcsl E(U). Ga, hafqofotd dfi pyevoyjom kidf agucageimg aj kce nuw-bjiavarg meioa, uv zizom U(O paf W) si yudduqc Bihlyrco’b ovrizoyfq.
Challenges
Challenge 1: Running Dijkstra’s
Given the following graph, step through Dijkstra’s algorithm to produce the shortest path to every other vertex starting from vertex A. Provide the final table of the paths as shown in the previous chapter.
Solution 1
Rigd wu P: A - (1) - Q
Yilp de H: A - (6) - G - (9) - B
Vazs ra N: U - (9) - J - (7) - R
Yoyr ta A: O - (8) - S - (8) - R - (1) - E
Challenge 2: Collect Dijkstra’s data
Add a method to class Dijkstra that returns a dictionary of all the shortest paths to all vertices given a starting vertex. Here’s the method signature to get you started:
fun getAllShortestPath(source: Vertex<T>): HashMap<Vertex<T>, Visit<T>> {
val paths = HashMap<Vertex<T>, Visit<T>>()
// Implement solution here ...
return paths
}
Solution 2
This function is part of Dijkstra.kt. To get the shortest paths from the source vertex to every other vertex in the graph, do the following:
fun getAllShortestPath(source: Vertex<T>): HashMap<Vertex<T>, ArrayList<Edge<T>>> {
val paths = HashMap<Vertex<T>, ArrayList<Edge<T>>>() // 1
val pathsFromSource = shortestPath(source) // 2
graph.vertices.forEach { // 3
val path = shortestPath(it, pathsFromSource)
paths[it] = path
}
return paths // 4
}
You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a kodeco.com Professional subscription.