27-09-2016, 12:03 PM
1456312304-shorteshpath.pdf (Size: 45.73 KB / Downloads: 12)
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.