16-09-2016, 11:16 AM
[attachment=71081]
“Shortest Path”
Given graph G=(V,E) with positive weights W(u,v) on the edges (u, v), and given two vertices a and b.
Find the “shortest path” from a to b (where the length of the path is the sum of the edge weights on the path). Perhaps we should call this the minimum weight path!
Greedy algorithm
Start at a, and greedily construct a path that goes to the next closest vertex from a, until you reach b.
Dijkstra’s Algorithm: O(n + m lg n)
Problem: it doesn’t work correctly if negative weights are presented. To compute the shortest paths between all pairs, we have to call Dijkstra’s algorithm n times.
Dynamic Programming
The problem can be recursively defined (by the subproblem of the same kind)
A table is used to store the solutions of the subproblems (the meaning of “programming” before the age of computers).
Designing a DP solution
How are the subproblems defined?
Where are the solutions stored?
How are the base values computed?
How do we compute each entry from other entries in the table?
What is the order in which we fill in the table?
Two DP algorithms
Both are correct. Both produce correct values for all-pairs shortest paths.
The difference is the subproblem formulation, and hence in the running time.
The reason both algorithms are given is to teach you how to do DP algorithms!
But, be prepared to provide one or both of these algorithms, and to be able to apply it to an input (on some exam, for example).
“Shortest Path”
Given graph G=(V,E) with positive weights W(u,v) on the edges (u, v), and given two vertices a and b.
Find the “shortest path” from a to b (where the length of the path is the sum of the edge weights on the path). Perhaps we should call this the minimum weight path!
Greedy algorithm
Start at a, and greedily construct a path that goes to the next closest vertex from a, until you reach b.
Dijkstra’s Algorithm: O(n + m lg n)
Problem: it doesn’t work correctly if negative weights are presented. To compute the shortest paths between all pairs, we have to call Dijkstra’s algorithm n times.
Dynamic Programming
The problem can be recursively defined (by the subproblem of the same kind)
A table is used to store the solutions of the subproblems (the meaning of “programming” before the age of computers).
Designing a DP solution
How are the subproblems defined?
Where are the solutions stored?
How are the base values computed?
How do we compute each entry from other entries in the table?
What is the order in which we fill in the table?
Two DP algorithms
Both are correct. Both produce correct values for all-pairs shortest paths.
The difference is the subproblem formulation, and hence in the running time.
The reason both algorithms are given is to teach you how to do DP algorithms!
But, be prepared to provide one or both of these algorithms, and to be able to apply it to an input (on some exam, for example).