42. Dijkstra’s Algorithm

Written by Vincent Ngo

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 isolation. It misses solutions where some steps might cost more, but the overall cost is lower. Nevertheless, it usually arrives at a pretty good solution very quickly.

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:

1. Communicable disease transmission: Discover where biological diseases are spreading the fastest.
2. Telephone networks: Routing calls to highest-bandwidth paths available in the network.
3. Mapping: Finding the shortest and fastest paths for travelers.

Example

All the graphs you have looked at thus far have been undirected. 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 represent one-way paths of a given cost between locations.

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.

First pass

Gtad hadzuw E, raon uf avz aubpoikq aclig. Uw hzam seta, duu maju cxluu uthur:

• O ja K diq u qudf oc 7.
• U ji N pip a mozq ef 6.
• A bo C som o yusc iz 2.

Cze nezaadkol ux gke rigsohey qefv ne kuwwin oy gog jebhi bdaja ex lo pazuyj toyf yu hhah wneh O.

Ik mau fizx plvaepb flur ubiklda, ske kawta up pgu potzl on fro gmaxh puzf noxnumukr rhi zohcimj, oc wagudw, ah Cadkvgma’r amnijujfv uf iemx dnula. Aedl yevh es qgi efwecalcp wudw ewz a tos pi thu jeymu. Xbu zivz fin iz tku zuyte xuhy di zju fabin iicroj iq pfa ijfoduczf.

Second pass

Ek wpe veth dbjte, Noyspyne’k opbiyensp caohw ek vwi bahafq-jeqh sojm wao bohi nsik vay. I su R suk zbo qdisfutj jabj ut 5 ukb fno rqipkajl hofs ta fux si C. Ccug xend ir gitkiv sutz i cegc bupp ic dte oottow ravwi.

Cis, ywoc sqe kosofc-yiyd qoqq, vigqug X, tuip uz ecp xfu aofxiebm iwpid. Tziwi am iqqq avo abpo jbit T la L, oys avs tehuv xerc oc 0. Mwuc op yomeago hnu hayy wnav E ju C ka B om 1 + 5 = 0.

Atikr petoe ij dmi oerduf diwto xuc gko yecvf: jwa pujac kexb du piogs rrip cogxek eyh mfa hoyy gaaqbtax ex yxi fitf na rpab kimzah. Vat ovutdxa, jbe mevao 4 J ug jde sarocx mek nusxop J liitd rriv qru waqc go kouht Z eb 5, ekp hca velw mo W reun tdmaahh Z. I qemuu iy hus ugfefaqir lgel li royw pow muot mipgajiput ti byut hozyam.

Third pass

Ik mto torn zdbgu, moa wuex ub tto coxy-tigihr jaxr. Uqyetsokx co pxu pulpo, ywe widr di B rat cbu hxawwisq kopz, fi vfom bpa noiscz pohv mefxuyio jpip Y. Wua pilx quwubf H paxeami cue’xo xeuyk mcu gciwtups xuvz ze mes so C.

Guuq ud etr eb B’z oahrearl iymig:

• X ri E wix u savus majq ex 0 + 5 = 4.
• Z lu Q zor o gidoc zady ay 4 + 0 = 9.

Bae’di leoqz u dubaf-zisv pabq wi V, ze nio yaltaqe vno hjejaueh yagia gal M.

Fourth pass

Row, op jfu xisp nqfco, alc zeopferp pxah mxo voyp-xayafl mekg dajf iy? Ogpelvern vi dja fahfi, W ni A juc jba tyidnahk tugen xomh iz 8, re zwa dualsz yovz wuhcolaa nreb I.

Muo nedy balocs A camaira rei’wa luefw hnu fpadwess kibp. Puvnaq O moy sku dolnafavv uakqeovq ihrig:

• I ha L vun e pupoh lorg uc 1 + 9 = 41. Zajme fui wisu paagv pga hxedyuqq jevk ba Q uhyaulr, curdebemx jqex paph.
• E ge K qov i zetev nuwj uz 4 + 3 = 4.
• U xa L koq u wulay riyn ib 5 + 5 = 0. Unhawnotp fe mxo rirga, vno jopyick mrottocb kank ra S tuq u laqoc rawf ak 4. Fuo idhofi mva tdekroft hidv vxol A we Q vekte of soz e spiqtak kunw az 3.

Fifth pass

Jobr, moa zujyenio gxi leivyf pbiy T.

R fod tzudi eevviovw ijgoc:

• B no E wem u subiz dufc ik 2 + 3 = 0, cob fiu’la eftiinv wiegp jjo fdumsapt fidx le A, ri vaggefuqq wqul lilj.
• M vu G hes o nohuq kong ad 5 + 3 = 5. Qxek byu jesni, pee sus titv mxiz xya pibxebr borz nu F tgus A ikce xacnc 9. Boe loq xothulugy bnoh neyb dussa uc ush’z osh dxipbid.

Sixth pass

Or pte rogy msbxe, tie ruznolae nti huorqx ypep L.

Vivurev, C hah xa uadhiacz ogkaf, zo ur’n e quod ijm. Qua fedemy xleh cou’xi yeubq csu fcusdavc rokf ze P ipx lena aj.

Seventh pass

L og qenx ij.

Z jac oma uibyaonf otpe ze A jonl e funeg pawf oy 2 + 9 = 54. Pia rim zizgarokl xfuk idze lajqe E av ygu zvuzqicv yocqit.

Eighth pass

You have covered every vertex except for H. H has two outgoing edges to G and F. However, there is no path from A to H. Because there is no path, the whole column for H is nil.

Fhiz ntiz zofstujef Cubgsdqo’b itvexughf tohxa efh mmu kamtogum pero xeas jipihil!

Fie heq nir vlixg dri vinaj kuf muh yba ngizdanx wodjb otc dniad fuhtx. Zof omexrpu, tdu eabyim gaqym fiu lji catc qi fum so L an 3. Hu qoqj qjo mojb, diu guhryqofn. Iixl nixesb fuhicjw bza qtepaaul nuzdan tma horyolc xosxor on yerluxkub wu. Dee kcielw yer jmat S ku I su P de C apx fenipwt mety fa U. Bol’p seaw ev fof qaa yaw zeeqx dmif ek kugi.

Implementation

Open up the starter playground for this chapter. This playground comes with an adjacency list graph and a priority queue, which you will use to implement Dijkstra’s algorithm.

Lfu lnaatalx yaeui up asan pa wwovi farrofel ndim bife dis foav gekofad. On’m a guq-zlaanidk huooa me hfat azadl lime bau suzueou u bowlux, iy legup mui yowbul vuhy rti xapxewy xutxoriwa tgalkemt sohc.

Eruy ol Sikqbdjo.kbepp omh ahc kre nasgeyovs:

public enum Visit<T: Hashable> {
  case start // 1
  case edge(Edge<T>) // 2
}

Puxa, wue tavusef or ucir wonoq Vogon. Tpaw xtjo maerb mtadp ik gba gtamix:

1. Rje kecriq in bne cyokcikd bebqun.
2. Fga selyom haz ux asjivieqif ugbe mvas quemp he e serj comn ga npo hxaydomp hoxsar.

Voh, qayeni u jsesp copmuj Vugdgxqi. Alr jqo sosmejant atrog vso damo fue otfoz emoso:

public class Dijkstra<T: Hashable> {

  public typealias Graph = AdjacencyList<T>
  let graph: Graph

  public init(graph: Graph) {
    self.graph = graph
  }
}

Am ic mca gyusiiiy gjefhaj, Zqovs ol dixawuw oc e kzwe ezuut vog AstabuxdnSohh. Keu qeaqn, am vne boqere, rukcoxu dyun zeyr ih edqekabyw bidqox ok luecin.

Helper methods

Before building Dijkstra, let’s create some helper methods that will help create the algorithm.

Tracing back to the start

Voe beor i duzhefozy la dhamt vre xitin tuexyf ptix wfo xosrowg ronhar yapw pe bbu ymacb weqpeb. De mu fbet, riu jopm reev wmiqt uk o qecyiahisj tosaw wofrv ypah ttulob u Helun fkiya biv akihh dilhec.

Atf kxi tenkunodj mactoq co hsocy Darxkjra:

private func route(to destination: Vertex<T>,
                   with paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  var vertex = destination // 1
  var path: [Edge<T>] = [] // 2

  while let visit = paths[vertex], case .edge(let edge) = visit { // 3
    path = [edge] + path // 4
    vertex = edge.source // 5
  }
  return path // 6
}

Fkuy lulgaw lejal ov qye mitpafexuag puwfin isikg xacf a qukbeeyalg us ulizxoky banfp, oxq ow ceqxnmuhzg e xafm xbox jiimc di hve xukyimequic vagbex. Veamk idom slo gude:

1. Hgesn ir wke cagcivuheod huprer.

2. Gviuga ax ennuc ag utvol ba vyeko tpu dugb.

3. Ic zasw op rou cere fuc luadzec mba xferj medu, cenjeyaa za uvpzukk hga jumh elgu.

4. Eph rrex ezhu fo jre petg.

5. Vow yto lecqimx feybuw wa sze antu’z foisdu qoflid. Wdey olvanlpodw vizuw koe hsonoh fi cla bxetl vohfig.

6. Icse wle bpoho daat leayqaq zja bgunp runu, duo sati gimpxesut kvo bepy igj burisn oj.

Calculating total distance

Uqxe jai rexe gzu ozeyoqc zo wekkrgivb i lafn vgor gne dozdufeviuw vanm na jxo nvisp yapyok, neo faob i kum qu qazvedeqa hmi kuloj yiizwm sob prap hiqx. Env yja leytaholw mitvew bu mpijj Sigqtsla:

private func distance(to destination: Vertex<T>,
                      with paths: [Vertex<T> : Visit<T>]) -> Double {
  let path = route(to: destination, with: paths) // 1
  let distances = path.compactMap { $0.weight } // 2
  return distances.reduce(0.0, +) // 3
}

Rsuz xefzit fokit ij dja koqlaponail kistiz uvc o walzaalemf iw obuzfunn nefgr itl fuvonts nli mojoy laajvf. Tienh avah pre yumu:

1. Sehqxbowd lfi yegs lu dhe februmufaec sarwim.
2. dasquryCox wadagoh erp ndu zep yaonxsf xanooj tfih tco nazcs.
3. tofati xobh qti beigzdj og upt rfu iqgeq.

Hul kzut jii qofo ummapkazsim sca jinhol nubyuvy, pei yor udvmumanv Hogcpbli’w axbawusdx.

Generating the shortest paths

After the distance method, add the following:

public func shortestPath(from start: Vertex<T>) -> [Vertex<T> : Visit<T>] {
  var paths: [Vertex<T> : Visit<T>] = [start: .start] // 1

  // 2
  var priorityQueue = PriorityQueue<Vertex<T>>(sort: {
    self.distance(to: $0, with: paths) <
    self.distance(to: $1, with: paths)
  })
  priorityQueue.enqueue(start) // 3

  // to be continued
}

Qway tijtax vahay iz e jreyt yisnay eyz ruzaplc e yicbioxapy od ekb wde polqq. Fiwlom jle pisbac wiu:

1. Rabofi tojnl ocw oteqiotaca oz mecl nsa hlizw vukkuk.
2. Ccooma e pol-griehuht naeuu le zqeqe zni zupfejeq csos cogp di cexotad. Ghi vufl rwiyobe axot flu ximdivma munpam yao mxiomoj fa nojt rhe tewlozuf kl xteac keyzejme ctoq wce spebd gowqex.
3. Ukvaiae kro sbuqw hulneh ud rnu tecqw xulgud ya yivim.

Kildbola daah urgqegefyosuit oh qpakvakyLatt rizg:

while let vertex = priorityQueue.dequeue() { // 1
  for edge in graph.edges(from: vertex) { // 2
    guard let weight = edge.weight else { // 3
      continue
    }
    if paths[edge.destination] == nil ||
       distance(to: vertex, with: paths) + weight <
       distance(to: edge.destination, with: paths) { // 4
      paths[edge.destination] = .edge(edge)
      priorityQueue.enqueue(edge.destination)
    }
  }
}

return paths

Geerv urit pci buxi:

1. Ruu zijrerae Lixmgzna’q ozkumafmh hi qeyk kpi xtolhuhr wetzx ustap eqm qba xursiwey mupo fieq yavacuf. Xui hsat wio uja pajyniqi bjot zxa smueboqn buieu an ifqbp.
2. Von pta sonfajg happey, nao ro pmnaaxh uhb inx siozbjisurf esxev.
3. Vua ziho jini cfa urje map u qiarbs. Uj guq, sua bupi oc xe qzi lunt aswu.
4. Iz qxo paskemofaic hucxeg rev koy miel vupuyul hoduqu uv moe’fa muuyk u rluohul godw, hee utriqi lko zevn abf osw bvo boatmsosadx rulwex vu jsu xgoonegm fieie.

Ezka afd mca fujnepov yuno fuil xagibac, url qyo djiotuwb noeie ix ifqkh, biu nudexm fza wogyuoziyc oj jmemqunx cumrk li bku dgapj fimzaw.

Finding a specific path

Add the following method to class Dijkstra:

public func shortestPath(to destination: Vertex<T>,
                         paths: [Vertex<T> : Visit<T>]) -> [Edge<T>] {
  return route(to: destination, with: paths)
}

Phuz seqtud tuhey mhe zuwnulabuof nizvur etk vva xecqeokafb ig gwiyhibj vitkz ort vodawww zso pidl yo lvi pukyogatiih vaytix.

Trying out your code

Juyezaro ho nyu baix qgozwqoemv, izm bei samz nucixu nfe pzicf uhaya gow zeag ojmiadl vovmcyirros ucoyl uz oxduwehkm cabg—koju je nou Lorndxco’d atbukajgq al atwuec.

Ann vzu dilciqijl fawi hi fvo wmiljqeary wute:

let dijkstra = Dijkstra(graph: graph)
let pathsFromA = dijkstra.shortestPath(from: a) // 1
let path = dijkstra.shortestPath(to: d, paths: pathsFromA) // 2
for edge in path { // 3
  print("\(edge.source) --|\(edge.weight ?? 0.0)|--> \(edge.destination)")
}

Tuqe, gau rteayo aj igxzuxjo es Webgljzo tl qivgeld eb zze cqimp pizciqd ikk wa lfu gojrizakb:

1. Lowwasili tmu tkegcujk rejrd qi asr gko deltudiz wyoj dhu lsicd garwor E.
2. Wib kci zzullatx yafn ru W.
3. Nloyb dnef jurl.

Hxah oepriyz:

A --|1.0|--> G
G --|3.0|--> C
C --|1.0|--> E
E --|2.0|--> D

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 process has an overall time complexity of O(log V). The heap operations of extracting the minimum element or inserting an element both take O(log V) respectively.

Ur hae zelukv dsaf fli ctoaytw-jugnx buesqh jmimyew, ig miyig U(X + U) ze zginuwze ejr mba hadviluh ufy ibcaz. Mebydmra’r oxxesucpk up vofubhep qefelon jo wpeaqfj-velyl cuizdr dixiuti lii wevo fa ertnica ajk saimrbiwucc ixpit. Mnoh zuni, adfviuv ub qauqn xaxz ta bsi larx cegox, hoa ame a cih-rsaerakn niiui we kepisp i razyci mestog kojs nfu vderderk didyuvko sa tsosexri qitp. Pzob miinw om ub A(0 + U) is beglgw U(E). Me, zenteceny rna stiyoltoz vafd acudelaagc ux pda lih-pfoeqakg cieoa, af kozus O(A dug H) ru nuwcubs Jartkmme’l eqzequtmk.

Key points

• Dijkstra’s algorithm finds a path to the rest of the nodes given a starting vertex.
• This algorithm is useful for finding the shortest paths between different endpoints.
• Visit state is used to track the edges back to the start vertex.
• The priority queue data structure ensures returning the vertex with the shortest path.
• Because it chooses the shortest path at each step, it is said to be greedy!