COMP 2140 Lecture 17: 11_14_path.pdf
13 Aug 2014
School
Department
Course
Professor
Document Summary
Initially, start node has cost 0 and all other nodes have cost. Update distances for nodes with edges from v. , set: set, while there are unknown nodes in the graph, select the unknown node with lowest cost, mark as known, for each edge with weight. // cost of best path to previously known. Features the cost of the shortest path to that node is known. The path is also known by following back-pointers. While a vertex is still not known, another shorter path to it might still be found. Interpreting the results from, say, a to e? vertex known? cost path. The shortest path from a to g? vertex known? cost path. , set: set, while there are unknown nodes in the graph, select the unknown node with lowest cost, mark as known, for each edge with weight known. While loop find an unknown vertex with lowest cost.
