27-09-2016, 12:03 PM
[attachment=71764]
Directed weighted graph.
• Path length is sum of weights of edges on path.
• The vertex at which the path begins is the
source vertex.
• The vertex at which the path ends is the
destination vertex.
Single Source Single Destination
Possible greedy algorithm:
Leave source vertex using cheapest/shortest edge.
Leave new vertex using cheapest edge subject to the
constraint that a new vertex is reached.
Continue until destination is reached.
Directed weighted graph.
• Path length is sum of weights of edges on path.
• The vertex at which the path begins is the
source vertex.
• The vertex at which the path ends is the
destination vertex.
Single Source Single Destination
Possible greedy algorithm:
Leave source vertex using cheapest/shortest edge.
Leave new vertex using cheapest edge subject to the
constraint that a new vertex is reached.
Continue until destination is reached.