Shortest Paths (concept)

Find the cheapest flight from Newark to London.

• DFS: “Can I fly from Newark to London?”
• Backs out when all vertices reachable from source have been visited
• BFS: “What flights from Newark to London have the fewest stops?”
• Shortest paths in an unweighted graph (hops/edges)
• What about the cheapest flights?
• BFS gets the shortest path with respect to edges (in this case, layovers), not weights
• Newark -> London (fewest edges) doesn’t consider cost – it’s the most expensive
• Need another algorithm to evaluate minimum-cost paths

Dijkstra’s Algorithm

Finds the shortest path (minimum cost) from a source vertex to every other vertex in a weighted graph, where all weights are nonnegative.

​

​

​

�Analyzes all possibilities for each neighbor of a vertex, picking the neighbor with the shortest distance from source.

It is a greedy algorithm: it solves the problem by making locally optimal decisions at each step with the hope to find the global minimum. (ie: finds the best distance at that time)

​

We can use Dijkstra’s to generate a spanning tree containing ideal paths from source -> others. (not in assignments)

Spanning tree = covers all vertices, no cycles

Dijkstra’s Algorithm

In a directed graph with n vertices and e edges

G = (V, E) where V and E are the sets with all vertices and edges respectively

Every edge weight must be nonnegative w(u,v) >= 0. Negative edges break the assumption of ideal distances (what if a negative edge gives us a better distance for a done vertex?)

​

Dijkstra’s Algorithm

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

Rather than visiting the first vertex (like in BFS), we pick the min distance vertex (min d(v) of vertices still in the fringe to be visited) + update based on distances

• Fringe: “to-do” list of vertices still yet to be visited
• Easiest implementation to find min: list (use this for assignment, O(n) linear search)
• Improvement: min heap (harder for assignment)
• pred(v): previous vertex on optimal path from source to parameter vertex
• d(v): optimal distance from source to parameter vertex (so far)
• If infinite: hasn’t been seen yet, hasn’t been in the fringe, essentially unknown

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

A

Fringe

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

A, B, D

Fringe (B, D newly added)

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

B, D, E

Fringe (E newly added)

d(b) = 6, d(D) = 1

D’s not-done neighbors: B, E

​

d(D) + w(d, b) is better than d(B)

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

B, E, C

Fringe (C newly added)

d(b) = 3, d(e) = 2

E’s not-done neighbors: B, C

​

d(E) + w(E, B) is WORSE than d(B)

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

B, C

Fringe

d(b) = 3, d(c) = 7

B’s not-done neighbors: C

​

d(B) + w(B, C) is WORSE than d(B)

dijkstra(A)

Algorithm:

let s be the source vertex

done = {} Vertices with known optimal path from source

fringe = {} Vertices with unknown optimal path from source

for each vertex other than source:

d(v) = infinity

pred(v) = null

d(s) = 0 Optimal distance from source to parameter vertex

pred(s) = null

add s to fringe

while the fringe is not empty fringe = to-do list, not ideal yet

m = remove minimum distance vertex from the fringe

add m to done set

for each neighbor w of m not in the done set

if d(w) is infinity then

d(w) = d(m) + w(m,w)

add w to fringe

pred(w) = m

else if d(w) > (d(m) + w(m,w)) then

d(w) = d(m) + w(m,w); pred(w) = m

endif

endfor

endwhile

C

Fringe

d(c) = 7

Every other vertex is done already

​

dijkstra(A)

Find predecessor to v on ideal path:

return pred(v)

​

Find ideal distance from source -> vertex v:

return d(v)

​

Algorithm to find an ideal path:

v = target vertex (most vertex)

path = []

while v is not null:

add v to path

v = pred[v]

reverse path to start from source

​

This algorithm is similar to find in quick-union: we can work with pred and chase through.

​

A -> D -> E -> C

Ideal path from A to C