Lecture outline for week 9 I. Shortest Path Algorithms - if we define the length of a path by the number of edges, use BFS - suppose we define a length (or weight) for each edge - define the length of a path to be the sum of the lengths of each edge - can we have negative edge lengths? - yes, but not a negative length cycle - a shortest path which goes through a negative length cycle has length -infinity - can a shortest path include a cycle ? (if no negative length cycles) - if length of cycle is positive, we can remove it and get a shorter length path - if length of cycle is 0, we can remove it, get a simpler path of the same length - so we do not need to include cycles - for our first algorithm, assume all the edge lengths a positive - given a source node s, let S be a set of vertices such that we know the shortest distance from S to s. - let d[v] be the shortest distance from s to v using only vertices of S as intermediate vertices on the path - assume w is the vertex with smallest d[] among all the vertices not in S - can there be a path to w from s which is shorter than d[w]? - assume there is - since d[w] holds the shortest distance using vertices of S, a shorter path must include a vertex x not in S - assmue x is the first vertex not is S on the shortest path from s to w - but to get to x from s we must go through vertices in S (since s is in S) - thus a path from s to w through x must have distance > d[x], but w has the smallest d[] of the vertices not is S - a contradiction - Dijkstra's Algorithm (Single source shortest path) - the algorithm implements the idea above - a priority queue is used to store the vertices and return the vertex with smallest d[] - in a priority queue, each element is given a priority and the element with highest priority is first out - algorithm: - let d[v] hold the distance from s to v, found so far - let pred[v] hold the predecessor to v on the shortest path from s to v, found so far for (i = 0; i < |V|; i++) { d[i] = infinity; pred[i] = NIL; (NIL is defined to be not a vertex) } d[s] = 0; for (i = 0; i < |V|; i++) add i to the PQ (priority queue) while (PQ not empty) { u = get next from PQ (u has smallest d[] value) for each v adjacent to u if (d[v] > d[u] + length(u,v)) { d[v] = d[u] + length(u,v); pred[v] = u; } } - note that Dijkstra's algorithm will not work if we have negative edge lengths (why?) - can we make the algorithm faster if we want the shortest path between 2 vertices and not between a source and all others? - no (why not?) - All-Pairs Shortest Paths (Floyd-Warshall Algorithm) - what if we want to find the shortest path between all pairs of vertices? - we can run Dijkstra's algorithm from each vertex - another solution is to compute a shortest path between every pair simultaneously - consider a shortest path from vertex u to vertex v - consider an intermediate vertex on the path, w - note that the paths u to w and w to v must also be shortest paths - let us label each vertex from 0...|V|-1 - let w be the highest labelled intermediate vertex on the path from u to v - then every intermediate vertex on the path from u to w and from w to v must have smaller labels than w - therefore if the path u to v has largest intermediate vertex label k, and if w is the intermediate vertex with largest label - then the path from u to w has largest intermediate vertex k-1 - consider the shortest path between u and v with largest intermediate vertex < 0 - only possible path is the direct edge (u,v) - consider the shortest path between u and v with largest intermediate vertex = 0 - only 2 possibilities: direct edge (u,v) or the path u -> 0 -> v - the all-pairs algorith - D[i][j] stores the length of the shortest path from if to j - M[i][j] stores the largest labelled intermediate vertex on the shortest path from i to j for (i = 0; i < |V|; i++) for (j = 0; j < |V|; j++) if (i == j) D[i][j] = 0; if (i,j) is an edge { D[i][j] = length(i,j); M[i][j] = i; } else D[i][j] = infinity; - note that D now holds the shortest path between each pair of vertices using no intermediate vertices for (k = 0; k < |V|; k++) for (i = 0; i < |V|; i++) for (j = 0; j < |V|; j++) if (D[i][j] > D[i][k] + D[k][j]) { D[i][j] = D[i][k] + D[k][j]; M[i][j] = k; } - at each iteration of k, D[i][j] stores the shortest path from i to j such that the maximum intermediate vertex label is k. II. Introduction to C++ - all ANSI C as you have learned in class is C++ - C++ just adds some additional features to simplify your coding - new type: bool - can be true or false - converts 0 to false and non-zero to true - nicer than using the #defines in C because we don't have to worry about multiple values for true - string type string s1 = "Hello"; string s2; - can copy strings directly: s2 = s1 - can compare strings if (s1 == s2) - memory for string is allocated dynamically - less efficient than a char array, but protects against hard to catch errors such as scanf("%s", c_array); - note that these are not C char arrays - if you want the C char array: s1.c_str(); - C++ has nicer I/O int d; char s[20]; cin >> d; cin >> s; - cin automatically detects the desired type of input cout << d; cout << "The total is " << d << " .\n"; - like cin, cout automatically detects the type for output - C++ has classes class stack { public: void push(int element); int pop(); stack() { top = 0; } ~stack(); private: int top; int data[20]; }; - the private elements can only be accessed by functions defined within the class - the public elements can be accessed by all parts of the code - stack() is the constructor - called whenever an object is created (by new or as a local variable) - ~stack() is the destructor - called when an object is deleted (by delete or when a local variable goes out of scope) - C++ can throw exceptions - C++ has nicer memory management - new and delete int *p = new int; int *c = new char[20]; delete p; delete[] c; - the delete[] is specific for arrays - Note that C++ does not have garbage collection - thus you must follow the same rules for memory management which you follow for C