Scribd
Upload
274 views16 pages

Dijkstra's Algorithm Explained

Dijkstra's algorithm is used to find the shortest path between a source vertex and all other vertices in a graph. It works for graphs with non-negative edge weights. The algorithm maintains a distance value for each vertex which is updated if a shorter path is found during relaxation steps. When the algorithm terminates, the distance value for each vertex will be the shortest path length from the source vertex. Dijkstra's algorithm can be used to solve problems like finding the lowest cost route between locations or detecting arbitrage opportunities in currency exchange rates.

Uploaded by

Andrei Necuţă
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
274 views16 pages

Dijkstra's Algorithm Explained

Dijkstra's algorithm is used to find the shortest path between a source vertex and all other vertices in a graph. It works for graphs with non-negative edge weights. The algorithm maintains a distance value for each vertex which is updated if a shorter path is found during relaxation steps. When the algorithm terminates, the distance value for each vertex will be the shortest path length from the source vertex. Dijkstra's algorithm can be used to solve problems like finding the lowest cost route between locations or detecting arbitrage opportunities in currency exchange rates.

Uploaded by

Andrei Necuţă
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 16

DIJKSTRAS ALGORITHM

Melissa Yan

Edsger Wybe Dijkstra


!! !! !!

!!

May 11, 1930 August 6, 2002 Dutch computer scientist from Netherlands Received the 1972 A. M. Turing Award, widely considered the most prestigious award in computer science Known for his many essays on programming

How do we get from 2-151 to Logan?

Single-Source Shortest Path Problem


The problem of finding shortest paths from a source vertex v to all other vertices in the graph. !! Weighted graph G = (E,V) !! Source vertex s V to all vertices v V
!!

Dijkstras Algorithm
!!

Solution to the single-source shortest path problem in graph theory


!! Both

directed and undirected graphs !! All edges must have nonnegative weights !! Graph must be connected

Pseudocode
!"#$%#&'('''''''' ' ' ')!"#$*+,-'$.'#./0,-'1-0$-2'"#'3-0.4' 5.0''*66'1''789#:' ''''''''!.''!"#$%1&';' ' ')#-$'*66'.$<-0'!"#$*+,-#'$.'"+=+"$>4'' ?' ' ' ' ')?@'$<-'#-$'.5'1"#"$-!'1-0$",-#'"#'"+"$"*66>'-AB$>4'' C7'' ' ' ' ')C@'$<-'D/-/-'"+"$"*66>',.+$*"+#'*66'1-0$",-#4'''''''''''''''' E<"6-'C'F' ' ' ')E<"6-'$<-'D/-/-'"#'+.$'-AB$>4'' !.'''/''A"+!"#$*+,-)C@!"#$4 ' ')#-6-,$'$<-'-6-A-+$'.5'C'E"$<'$<-'A"+G'!"#$*+,-4'' ''''''??9/:' ' ' ')*!!'/'$.'6"#$'.5'1"#"$-!'1-0$",-#4'' '''''''5.0'*66'1''+-"H<I.0#%/& ' ''' ''''''''''''''!.''"5'''!"#$%1&'J'!"#$%/&'K'E)/@'14' ')"5'+-E'#<.0$-#$'B*$<'5./+!4' '''''''''''''''''''''''''$<-+''''''!%1&'!%/&'K'E)/@'14 ')#-$'+-E'1*6/-'.5'#<.0$-#$'B*$<4' ' 0-$/0+'!"#$' ' ' ' ')"5'!-#"0-!@'*!!'$0*,-I*,L',.!-4'

Output of Dijkstras Algorithm


Original algorithm outputs value of shortest path not the path itself !! With slight modification we can obtain the path Value: (1,6) = 6 Path: {1,2,5,6}
!!

Why It Works Intuitively


Lemma 1: Optimal Substructure The subpath of any shortest path is itself a shortest path. !! Lemma 2: Triangle inequality If (u,v) is the shortest path length between u and v, (u,v) ! (u,x) + (x,v)
!!

Proof of Correctness 1
!!

Invariant: d[v] " (s,v) for all v V


!! Holds

after initialization and any sequence of relaxation steps

Proof Hint: We will need the relaxation part of the pseudocode. d[v] " d[u] + w(u,v)

Proof of Correctness 1.5


!!

Relaxation step not only maintains the invariant but allows us to find next shortest path Suppose s # ... # u # v is a shortest path
d[u] = (s,u) !! And we relax edge (u,v) !! Then d[v] = (s,v) after relaxation
!! If

!!

Proof

Proof of Correctness 2
!!

When Dijkstra terminates, d[v] = (s,v) for all v V

Proof Hint: We will need min-extraction part of the pseudocode. u #mindistance(Q,dist)


!!

Applications of Dijkstras Algorithm

Why do we use Dijkstras Algorithm?


!!

Algorithms for calculating shortest path from source to sink about as computationally expensive as calculating shortest paths from source to any vertex

Currency Exchange Problem


Is there an arbitrage opportunity? !! Ex. $1 # 1.3941 Francs # 0.9308 Euros # $1.00084
!!

Currency Exchange Problem (con.)


Vertex = currency, edge = transaction !! Weight = exchange rate !! Find path that maximizes product of weights # reduce to sum of weights !! Is there a negative cost cycle?
!!

Bellman-Ford Algorithm
!!

Works for negative weights


!! Detects

a negative cycle if any exist !! Finds shortest simple path if no negative cycle exists If graph G = (V,E) contains negative-weight cycle, then some shortest paths may not exist.

You might also like