31251 Lecture Notes - Lecture 9: Shortest-Path Tree, Dynamic Programming, Prims

48 views2 pages
Dijkstra’s Algorithm
The backbone algorithm for most shortest path algorithms.
Employs a dynamic programming approach.
It’s not too far removed from Prim’s algorithm
It builds a shortest path tree instead,
but a basic greedy approach doesn’t work in deciding which edge to add.
Doesn’t handle negative edge weights (in the basic version).
Given a graph G with non-negative edge weights, with a given
starting vertex u:
1 Set the tentative distances for all vertices; 0 for u, infinity for all others.
2 Mark all vertices as unvisited.
3 Set u as the current vertex.
4 While there are unvisited vertices:
1 For each unvisited neighbour of the current vertex:
1 Compare the tentative distance to the neighbour with the distance to current plus the
edge weight of the edge joining them.
2 Keep whichever is smaller.
2 Mark the current vertex as visited.
3 Select the unvisited vertex with smallest tentative distance and set it as the current vertex.
We can keep an array of predecessors that gets updated when we update the distance
this will give us the shortest path tree.
We can keep an array of predecessors that gets updated when we update the distance
this will give us the shortest path tree.
Where was the dynamic programming?
When we select whether to update the distance or.
If dist[v] is the distance from u to v, then the core of the algorithm is repeatedly
performing
dist[v] = min{dist[v], dist[current] + w(current, v)}.
Note there’s also a greedy selection of the next vertex to process.
Where’s the problem with negative edges?
Dijkstra’s Algorithm – Correctness
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Unlock document

This preview shows half of the first page of the document.
Unlock all 2 pages and 3 million more documents.

Already have an account? Log in

Document Summary

The backbone algorithm for most shortest path algorithms. It"s not too far removed from prim"s algorithm. It builds a shortest path tree instead, but a basic greedy approach doesn"t work in deciding which edge to add. Doesn"t handle negative edge weights (in the basic version). Given a graph g with non-negative edge weights, with a given starting vertex u: 1 set the tentative distances for all vertices; 0 for u, infinity for all others. 1 for each unvisited neighbour of the current vertex: 1 compare the tentative distance to the neighbour with the distance to current plus the edge weight of the edge joining them. 3 select the unvisited vertex with smallest tentative distance and set it as the current vertex. We can keep an array of predecessors that gets updated when we update the distance this will give us the shortest path tree. When we select whether to update the distance or.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents