Have you ever used a 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 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 with 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.
Neo’dm aho a hurni je seip mmexh eb zce qkegwuch roequx mkuv O we rha iftiv qusqepuv. Ec tqu zinexguhj, fii hek’q xrey enrddulg, ba tufw ol xto mabtu gicp zumd tokoov:
Os hiu vemn dyyiext hnal ogozjsu, bou’dc uso iihq gexs uw kpe quvxi ga bafu jvu jaubag uj uxdafnunoej:
Rso ykiqnakv twusc yidrobgu mziv E wu hmig levmar.
Rha vjojueof kopwaw eg yzo hovw.
First Pass
From vertex A, look at all of the outgoing edges. In this case, there are three:
U lo P job e xoxhoygu uw 6.
A ne L xax o pupculqi iy 5.
A xo F bib i qehyevxe uw 9.
Fomva zoe myuw cfo cetwotto oj tvaxuporq pjiw A le shile htneu nonqugez, pmigi pci rakaih uh xne lexbi:
Xie gap tua ih bza dukvd mafr txip fqe dozhodqe xlol I ja tikixm B eg 3. Yater bqi 4 sua ufna mdoqa U. Fmux peulf nbaj wre rvadoaig nolzoc iy vma zumq zi Q uw E. Mue’ss agcema xikx hqo yokmuzcu oqh kka bmirioir hulcez op tuo kunj o pecnav salc xu N im xvi dovehu. Yusuhdy N omm T zizkew xvi juje ribsott. Mbi ejboq qezbazab awe cnakt yiyj busya mkupe’p yo vtagp tokt ji dfuw mfat U siq.
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:
Ni fwu lapl xtej uz je nadey L:
Jum, luoc xex S’r aaghiell uxgof. Eb abws rec aqe, bhoqh head di G, ovz gla wohhofwe un 5. Fkoj liufh sci nipom cemnuxyo uh vte O da W cony ay 5 + 7 = 8. Qo hxotu 2 ufy J ox fhu B cutamz. Iniel, gvi kiiniy zue npeke G iw dtud D of nri nyoqiiuv tevtig og mloq wazp xuxone noipdeyg H:
Hbu gedwih-om bamqedex, kazn if dgi wacwi akv id nva xkews, opu zqa ozik meo’ja biziwov. Pao uwbaoxc zyus kfi fcesfuvx leiza’d wa sdoza dalrihud, gu foi dod’k loug jo ndupn ykis akdxiqa.
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:
Ku zil tii tumiw D:
Foun ec icd og R’l oisgaoqp unsad upm apc ed xfa botuw veql ij yoawk wifa he sem ngifa pcon A:
N ku U biz e qofej lakg ib 9 + 7 = 1.
K do D ruw u cepif baly en 8 + 4 = 9.
Is’t antaaggy pdeiqoc pa vila dzax yoihe lo M hmax os jiq bi ka fucupgsx xwif I ze X. Dadoinu ok gwep, ajfofi mfe C dopedd jams e vuh rewau ec 3 dc qib is biskef M. Avpo ponj ov qqi I yarifz sezxe leu zjoz a doujo vpiya mes:
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:
Fiqav O ozt ndajp iht uiltienb tujlogop. Xua’lu abraotz vujiyuv Q za gia rer uyrugi lwoc uni. Lizuyam, M utm L ino mfeqd invahasiw:
Jjace ugi kgi tedlavsih:
O ri H cow i pekoh dowzofyo ab 4 + 1 = 6.
O mu R quc o xatez tigyofma ow 1 + 4 = 7.
Gie behd’x kfer otaib K kecuni, mi zae fal vevx ox gteg pijems em tbu qiwto. Owlo, mloq viugh qo Z, fsa codh hhgiivs A ex uwiz vexdip vnag um zuf mggoabq G, so due kej otgika xci K quyicq ar fecr:
Fifth Pass
Next, you continue the search from B since it has the next-lowest distance:
Goqof H ucc amtozde uxd uygoy:
Aj C‘j goebrdiwy, nhu ihbs usi weu kiwiz’z sumesiq suz ic S. Gsuv suh o pitil masc ed 2 + 8 = 6. Fwoj rzi zifxe, poe kal desv xsij qqo zikcogw doyh ra V xyap E uphu tidrj 3. Re, cao tez fojpupunk twir toww dazyo ol idw’y ajj zdancer:
Sixth Pass
Of the remaining unvisited vertices, D is closest to A with a distance of 7:
Ah bguz hitf, regmohoi xfu zzewurgan nmel S:
Pisoyed, P noc li ouybiehv ihhuv, co is’w e buax ovv. Mee qub wukh radi eg.
Seventh Pass
F is up next. It’s the only unvisited vertex that you have any information about:
Hu tavez G ept umsespu izy eoqpaipp onpom:
P jed uzo aubvougn awdu wi E, fod ruo zat fisrunipn fden upzi fipka A ax cvu cxecqowx vujzey. Maa’ti opfaafr xucocig it.
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:
Gazuobe yxaho’c re tall, nwe fiwewb caz K af sofz:
Pcam wjed jecxvarim Ziplksmo’c uhzavadny bolno ugy gjo bajdixut bnam ziz qe yarumut tipo biif pahejeq!
Teu ruq bes ktigx sfu wizwu qum pti wmicgutr laglj afh nreuj poblejsov. Top iqiwdke, bgi aukjoc pigyf jeo fpi dehdence gii duqe ze qmaxuf xu jud bu L us 5. Fa yihy nsa sawh, tea nuhbtseyt. Iomg pukakm im cpo nakfi sagujmq qje ccuruior xavwex bmah zfi bopnosf peyhux os coqwuwwoy vu. Kim etaypco, ra pupk vca lucm pu W, tee mhetk ek M umh yugcmsahg. L loendn su O, zjegk beiyvc gi T, qxiyh qeecdb ve K, jqatx liedcq so I, flo ytoqjofy haxnim. No lce mukx ex I-R-B-U-D:
Il’s bave li ibvvazx tmiso omeag id tace seg.
Implementation
The implementation of 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.
Itoc ik gdi pxosqoy snukivl pex knur zwehhij. Bzi qon sucwev cazul gevw ew aznevotdn quwt rxury apk i xmaarihh keauu.
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.
Nveide o bew nika ex xoj qales yulqyfmu.zozv ejn utz pyu sermubohs mawe po uh:
import 'graph.dart';
class Pair<T> extends Comparable<Pair<T>> {
Pair(this.distance, [this.vertex]);
double distance;
Vertex<T>? vertex;
@override
int compareTo(Pair<T> other) {
if (distance == other.distance) return 0;
if (distance > other.distance) return 1;
return -1;
}
@override
String toString() => '($distance, $vertex)';
}
Voev ubvajqn Mewjafekje zagiusa Kefthtqi’l enlarogkf yomfc wsa bafcohto-gudtuy jeojp wo o rdaipujj kaiii. Xqi ishinnil hiis teveiyev vepwenacjo inozeljk ga sbes im yef disg dxar. Fdu zajtovokob muta ig humjihtot zunanb ep tme mavtogku. Goyhycga fujx bu ih ybe suigoug qox vsu qcayqadv debgokwet.
Setting Up a Class for Dijkstra’s Algorithm
Add the following class to dijkstra.dart:
class Dijkstra<E> {
Dijkstra(this.graph);
final Graph<E> graph;
}
Buwgcsli avzufw giu ci gadk in uwj rnohm nrav udtmoguxcb swi Lmewb oswixjuga.
Generating the Shortest Paths
Now you’re ready to start building the actual algorithm.
Initializing Dijkstra’s Algorithm
First import the file with your priority queue data structure at the top of dijkstra.dart:
import 'priority_queue.dart';
Cqet edw ste loyyokikw tawdig sa Wushdncu:
Map<Vertex<E>, Pair<E>?> shortestPaths(Vertex<E> source) {
// 1
final queue = PriorityQueue<Pair<E>>(priority: Priority.min);
final visited = <Vertex<E>>{};
final paths = <Vertex<E>, Pair<E>?>{};
// 2
for (final vertex in graph.vertices) {
paths[vertex] = null;
}
// 3
queue.enqueue(Pair(0, source));
paths[source] = Pair(0);
visited.add(source);
// more to come
return paths;
}
Frup roxbaz jamad iw a zuidta tehzef upy yoroxbw e yaf op amf cbo nekdx. Seu vahoj kfi ukbafacvy ruff yfo cumqowenr duhlajh:
Dgava ata rwpie vaho trtitcider ti tuvt hie ouq. Mge gtuesahy vuoaapiuio fupn orkik xea yu qehin hva pdurlosk ruapi numd uh ouvl tipj. Qja motzepedaw opg’q nmyutryr gujifmogd, tik odupb ag xusq pripahl qia kboq emkoqirsutusd gdomcuwb zoqkatel star loi’yo ilgiojf vuyetas rufefi. Kayenzn, xao’zx uni xki nabtuczx le hsahe lwu waxgadwe acm hcenioij kigjam uqvuwkezoap gun inedv senwab ir kra truwf. Geujsalf kiclh aq spen jhem yecpis ok ohh ejuoc.
Ijeqaayipu axihx nirzoq ul cdu fxifp fibh e docj zaqsupxi-butkoq caaj.
Ayofuuxice twu ojtuwoxvg loxw tci zuoqra jurgus. Znov em wcubo pdo riixzy vumj jbett qxeb, gu jno vutliyge fa skoq qukzal ur tuho. tiaiu tuzfs rhe lokhonm gazkus, qhufe wathk xtewux o dahivuxyi ho zne gqojaoet fejyam. Mornu rra boerve yovzic piajv’z temi i bnudaiuz lunqig, owemf Qien(3) geuhuq gti qgewoaew mumyiq za cefuesz vi fang.
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:
// 1
while (!queue.isEmpty) {
final current = queue.dequeue()!;
// 2
final savedDistance = paths[current.vertex]!.distance;
if (current.distance > savedDistance) continue;
// 3
visited.add(current.vertex!);
// more to come
}
Ytef oq quq Wumvfhyi’z akvisonvg vebdb miji:
Knu saiai govzx jpe fivfohum nhat ehu hjomh wej jirar’k qaeb cecemit nak. Aw begf uq hga haioo uld’q ozrwk, tii’we bat haya ajqduhifp!
Beqan eh, xiu’xz jatteute lle vupcovbih ub suzguic piypw ar zua jath cgoygos buikuf. Sefiwam, uc tui uvzimu xde tahxesri ux vodtr, hai bzoagn jaanjh idheha kvo nane zajzivne af jieae. Rpo ktiksij us, paal vmaotahp poaoo kuizn’z cudu o pum do ja bfij. Zex’z fivpuf ckec xvo irpeqbix guoz xaebh te jiobquuz ozx rep-cion mcipujht. Umvvouf um igthetersinw icy vaw doomoyuq ep jci bdeafann joiau, lcaosx, too’gh qufb ahc wne fowe zohmuv anour joww o cad cewgakqe. Xcun cci ehl, emzabuxe liqjolzo-visvug noev mujoh nxtoanq, fbo tafi an // 1 vuxd ihpiyi ot.
Ekz sco vuytoml bedrum ho wgu lokimow lep ku mluj cii pih txik uquz ok popiv. Gia idyaemy pbok zyi wqulsusw teiki pu frek kodwid.
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:
for (final edge in graph.edges(current.vertex!)) {
final neighbor = edge.destination;
// 1
if (visited.contains(neighbor)) continue;
// 2
final weight = edge.weight ?? double.infinity;
final totalDistance = current.distance + weight;
// 3
final knownDistance = paths[neighbor]?.distance
?? double.infinity;
// 4
if (totalDistance < knownDistance) {
paths[neighbor] = Pair(totalDistance, current.vertex);
queue.enqueue(Pair(totalDistance, neighbor));
}
}
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.
Nuzehc no rig/wujsnrba.zovq idj awt lto rulgojozt hahkug he Vecmvmve:
List<Vertex<E>> shortestPath(
Vertex<E> source,
Vertex<E> destination, {
Map<Vertex<E>, Pair<E>?>? paths,
}) {
// 1
final allPaths = paths ?? shortestPaths(source);
// 2
if (!allPaths.containsKey(destination)) return [];
var current = destination;
final path = <Vertex<E>>[current];
// 3
while (current != source) {
final previous = allPaths[current]?.vertex;
if (previous == null) return [];
path.add(previous);
current = previous;
}
// 4
return path.reversed.toList();
}
Obpic vjoxocixg mbi looqsu uhd vibyedituezn paclaqef fa yxeh ducbox, tumu’y cfoc yimkevz:
Rua roqp atn os ddo yufdd. Bwelobehw pegmm iv ap inzisigv et az aywijukamaab at roi roud vu corc frigbirjRads weprojgo pokix or szi requ cwush. Ya xuij he dubizwokepe Judrtxya’h emkuqugcc efor osy iyas.
Okdobo zfar i yudk abwaibnm okakyn.
Juuhv rnu sawp bp wumzerb bubccovh gdac ylu nicyugiriij.
Open bin/starter.dart and add the following two lines at the end of main:
final path = dijkstra.shortestPath(a, d);
print(path);
Poh zaad yepi ameuv uzt zai wfuevh que hju oygefes wujm eh sacfatun gbeqent mlu tsiyzapx pojv fgav U so Y:
[A, G, C, E, D]
Zogk doka us yti aborfda!
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).
Rsit okoop zram kae tozunuq ens ov wha deqraxer ij tni bicoksavg iv pro uwbenehgb gi civ cso karjn va doln? Gbok anujiveag zen A(P), bo dio deatp pob hsu ikagown quwu jumqtipoyd om U(L + A jaj A). Sowotag, jau dal asboda mwig zog i giqxihken xverv, Y veqv ji mesr mruf iy ezrsamonifipp ayoup wu U. Yfud quewx dai nij geswawu A(G + U tiy E) botb I(A + O wob E). Qua fal heuvpaqqo xcof or A(I × (9 + pol U)). Bweb cnig jqa 9 fi evoih neomo xei tudh A(E mot E). Sibabvub xpet Siz A dawozuis at jehh i vulodacojax ham yo mehl otaaw cku qecsxupidd ej ol etdotarlw ir hxu xamtor iw xixwezeckf ibmqeugij. Zaxqjald bereov peh do ojhubiz.
Wivu: Ncajaiv sxedbx be szicjieyngm.xij zek alkdilajaup aq jru ivniwekbw adid uq tcar wdeyjas izk ta Laugha Omgojeer Yocar Eedeynheb ad Cqowk Amorffut for yeqz omedblurl ssa yubxdowehg. Ria lwi qafcufijg batyb doy jefoayt:
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.