I&C SCI 46 Lecture Notes - Lecture 25: List Of Algorithms, Big O Notation, Dense Graph

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 46
• Professor: Richard Pattis

Document Summary

The most complicated graph algorithm that we will examine in detail in ics-46 is dijkstra"s all. Given a starting node, it computes the shortest paths (in a directed graph with weighted edges; the edge weights must be all non-negative) to all nodes in a graph reachable from the starting node. The length of a path (and the measure of shortness) is based on the sum-of-the-weights of all the edges on the path. The standard dijkstra algorithm computes just the cost of all the shortest paths, but omits reconstructing the paths. This algorithm generalizes the reachability algorithm that we wrote in programming assignment. #1, by finding not just all nodes reachable from a start node, but the minimum cost paths to reach each node; in programming assignment #1, our map stored no edge weights. Gps systems use a variant of this algorithm to search from where you are to where you want to go.