CSC152 2006S, Class 52: Finding the Shortest Path in a Graph Admin: * Questions on the exam will happen at the end of class (or after class). * As we have a visitor, I will use the EBoard to record my notes on the class. * I will do my best to get you preliminary grades by next Wednesday. * EC for attending any one of Ben's four baseball games Overview: * Some Definitions (Path, The Problem). * A Simplified Version: Shortest Paths in Unweighted Graphs. * An Example. * The Solution. * Extracting the Path. * Weighted Graphs: Dijkstra's Algorithm. * Asymptotic Analysis. /What do you know?/ * Graphs have vertices and edges. Vertices are 'stopping points' and edges provide connections. [Good definition from LH] * Edges may be directed /An Example/ +----------------+ v | v0 --> v1 ----> v4 ----+ | | ^ ^ v | | | | v3-+ | | | ^ +----> v2 ----> v5 ----+ /Definitions/ * Definition: A path is a sequence of edges that take us from one vertex to another. * The cost of the path is * The number of edges, in an unweighted graph * The sum of the weights of edges, in a weighted graph * The problem: Shortest path * The cost of the path is less than any other path * We find *a* shortest path, since there may be multiple such paths /Strategy/ We actually solve a harder problem: Find a shortest path from a vertex to *every* other vertex Build a table of three columns: Vertex | Distance/Cost from v0 | Predecessor -------------------------------------------- We can fill in the distance to v0, since we start at v0. v0 | 0 | NONE For all neighbors, we can compute the distance to those values v1 | 1 | 0 v2 | 1 | 0 [Suggestion from class: vertex 3 is 3 because we can count the edges. Problem: Computers can't just count the edges. We need to instead think about how the computer will do the work without knowledge.] In this case, although v3 comes next, we can't fill it in immediately. Instead, we fill in the neighbors of v1. v4 | 2 | 1 We then fill in the neighbors of v2 v5 | 2 | 2 Finally, we fill in a neighbor of v4 v3 | 3 | 4 Putting it together: Vertex | Distance/Cost from v0 | Predecessor -------------------------------------------- v0 | 0 | NONE v1 | 1 | 0 v2 | 1 | 0 v3 | 3 | 4 v4 | 2 | 1 v5 | 2 | 2 [Student comment: Since there's an edge from 3 to 1, might we need to recheck that value? Answer: Let's consider the pseudocode.] /Pseuocode/ Initialize for all vertices, v, dist[v] = infinity pred[v] = undefined Main Loop for all possible costs for all v where dist[v] = cost for all w adjacent to v if dist[w] = infinity then dist[w] = dist[v] + 1 pred[w] = v /Java Code (inserted by Sam)/ // for all vertices, v, for (int v = 0; v < n; v++) { // dist[v] = infinity dist[v] = Integer.MAX_VALUE; // pred[v] = undefined pred[v] = NO_SUCH_VERTEX } // for all possible costs for (int cost = 0; cost < n) { // for all v where dist[v] = cost for (int v = 0; v < n; v++) { if (dist[v] == cost) { // for all neighbors for (int w) in graph.getSuccessors(v) { if (dist[w] = Integer.MAX_VALUE) } } } } /How do we read off a path from the table?/ * For example, what is the shortest path to 3? * Go backwards: * To get to 3, you need to have come from 4 * To get to 4, you need to have come from 1 * To get to 1, you need to have come from 0 * Therefore, the path is 0 -> 1 -> 4 -> 3 /A Revised Example/ +----------------+ 4 v | v0 --> v1 ----> v4 ----+ |6 | ^ 5 ^ 1 v | |1 2| | v3-+ | | 4 | 3 ^ +----> v2 ----> v5 ----+ Assumptions * No negative weight edges * Once again, the strategy is to Goal: Given a directed, weighted, graph where edges have non-negative edge weights, find the shortest path from vertex 0 to vertex i for all i. ["Shortest" means smallest sum of edges.] Vertex | Distance/Cost from v0 | Predecessor -------------------------------------------- v0 | 0 | NONE What's the shortest path to v2? It seems to be 1. v2 | 1 | 0 Is the shortest path to v1 the edge from v0? NO! A problem: When we choose a vertex, we don't want to process it too early because, if we update it, we will then need to update its neighbors (and all of their neighbors and so on and so forth). Hence, we mark a vertex when we are CONFIDENT that we know the shortest path. Add a column "known" Vertex | Known | Distance/Cost from v0 | Predecessor -------------------------------------------- v0 | | 0 | NONE v1 | | 0 | NONE v2 | | 0 | NONE v3 | | 0 | NONE v4 | | 0 | NONE v5 | | 0 | NONE How do we know when the shortest distance is known? * If there's only one predecessor (one not thought of; a good idea, but not workable for all nodes) * Try every path to that node (workable, but *EXPENSIVE*) Hmmm .... what can we do? Let's try working the algorithm v0 | X | 0 | NONE We now have tentative costs for two vertices, the neighbors of 0 v1 | | 4 | 0 v2 | | 2 | 0 For vertices with tentative costs, we have a known cost and a number of other possible, non-explored paths. Can we be sure of any of them? Consider the vertex with a least tentative cost. Any other path to that vertex will have to go through one of the other tentative vertices. Since the costs to get to those vertices are all larger, using them won't help. [Hmmm ... should I ask the students to finish the example on their own?] Sketch algorithm: We repeatedly select a vertex to "process". When we process a vertex, we mark it and update the costs to all of the neighbors Initilization for all v, known[v] = false; dist[v] = infinity pred[v] = undef dist[0] = 0 Update for i = 0 to n-1 v = "find vertex with lowest tentative cost" known[v] = true for all neighbors, w, of v if dist[w] > dist[v] + weight(v,w) dist[w] = dist[v] + weight(v,w) pred[w] = v [Sam decides not to record walk-through so that he can put something similar on the final exam. Hint hint.] /Asymptotic Analysis/ Initialization is O(|V|), |V| is "number of items in the set V" How long does it take to find the vertex with lowest tentative cost? O(|V|). We do so O(|V|) times. Total cost: O(|V|^2) How long does it take to look at adjacent neighbors? For a particular vertex, it is potentially as bad as O(|V|). That means that identifying adjacent neighbors would be O(|V|^2). However, we follow each edge exactly once. Hence O(|E|).