Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision |
| courses:cs211:winter2014:journals:alyssa:chapter_4.4 [2014/02/26 02:44] – created hardnetta | courses:cs211:winter2014:journals:alyssa:chapter_4.4 [2014/02/26 02:49] (current) – hardnetta |
|---|
| |
| ===== Dijkstra's Algorithm ===== | ===== Dijkstra's Algorithm ===== |
| This algorithm maintains a set //S// of vertices //u// for which we have determined the shortest path distance //d(u)// from //s//. We call this the "explored" part of the graph. Initially, //S={s}// and //d(s)=0//. For each node //v// in //V-S//, we determine the shortest path that can be constructed by traveling along a path through the explored part //S// to some //u// in //S//, followed by the single edge //(u,v)//. We consider //d'(v)=min_e(u,v) d(u)+l_e. We choose the node //v// in //V-S// for which this quantity is minimized and add //v// to //S// and define //d(v)=d'(v)//. | This algorithm maintains a set //S// of vertices //u// for which we have determined the shortest path distance //d(u)// from //s//. We call this the "explored" part of the graph. Initially, //S={s}// and //d(s)=0//. For each node //v// in //V-S//, we determine the shortest path that can be constructed by traveling along a path through the explored part //S// to some //u// in //S//, followed by the single edge //(u,v)//. We consider //d'(v)=min_e(u,v) d(u)+l_e//. We choose the node //v// in //V-S// for which this quantity is minimized and add //v// to //S// and define //d(v)=d'(v)//. |
| |
| This can be clarified by the pictures used in the lecture slides. | This can be clarified by the pictures used in the lecture slides. |
| |
| Using a priority queue, Dijkstra's Algorithm can be implemented on a graph with //n// nodes and //m// edges to run in O(m) time, plus the time for //n// **ExtractMin** and //m// **ChangeKey** operations. So the overall running time is O(mlogn). | Using a priority queue, Dijkstra's Algorithm can be implemented on a graph with //n// nodes and //m// edges to run in O(m) time, plus the time for //n// **ExtractMin** and //m// **ChangeKey** operations. So the overall running time is O(mlogn). |
| | |
| | I would rate this section an 8. It was easy to read but the lecture was easier to understand. |
