|
Quick Links
Calendar
Categories
Archives
Statistics
Total entries in this blog:
Total entries in this category: Published On: Mar 21, 2005 03:19 PM |
Lecture 28Today I began a sequence of lectures
dealing with paths in graphs. We consider a connected graph as input and want to
determine the costs of shortest paths from single source to all other vertices.
We will consider this problem on directed, and undirected graphs, and when the
edge weights are arbitrary positive values, or all 1.
Today we saw the main ideas behind a greedy approach that determines a new shortest path value at each iteration. On Wednesday I will flesh out the details. This includes an argument to justify the correctness of the greedy approach. We will also consider efficient implementations of the algorithm. The algorithm we discussed today goes by the name of Dijkstra's algorithm. A very nifty applet that demonstrates this algorithm can be found here. This material is covered in Chapter 15 of the text. Posted: Mon - March 21, 2005 at 03:13 PM |
||||||||||||||