In this lecture, we are going to introduce the shortest path problem. What is the shortest path problem and why is it important? What is the shortest path problem? You can guess what it is. You are given a weighted directed graph. Let's put some cycles in there, no problems. You are given a graph, and the graph has weights on the edges. It can even be negative weight. It has weights on the edges. Suppose I have a source and I have a destination. You ask the question, what is the least weight path from the source s to the destination t? You want to know what's the path of least weight and what's the weight of a path? Suppose I go directly from s to t, the weight of this path would be the weight of the edge s to t, which is 1. Now suppose I go from s to a, a to b, b to t, then the weight of this path is 2 plus 3 plus 1, which is 6. Suppose I go from s to b, and b to t, the weight of that path would be 2.5 plus 1, 3.5. What about the negative edge here? Maybe I can go from s to a, a to b, b to d, d to a, a to b, b to t. But that makes no sense because if I pick the cycle here, 3 plus 1 minus 3.5. If I take this cycle here, then this cycle is going to have an extra weight of 0.5, so it makes no sense to take cycles. We will see this formula in a second. The least weight path from a source to a destination and this is a very important problem. Every time you log onto Google Maps, you are entering a source address from, you are entering a to address and you get a route to go from your address, from address to address. That's an instance of the shortest path problem. Now, the interesting thing about that is what are the weights in your graph? What are the weights? The weights can be traveled times. The weights can also depend on congestion, how much traffic is there? The weights can also depend on the distance. Even though travel time is correlated in a positive sense with distance, it doesn't necessarily mean that as the distance increases, travel time also increases monotonically. Sometimes the distance can increase in that travel time can decrease because you are traveling on a faster high way with higher speed limits, at higher speed limits. It depends really. Google gives you the option. It gives you the option to sort. Google gives you the option to choose distance or choose travel time. It's an interesting thing and it's actually more sophisticated, way more sophisticated than the shortest path problems that we are going to study in this class. But what we are going to study in this class forms the foundation for understanding everything else. It's going to be important. Where else are our shortest path problems solved? Well in a lot of other places as well. Shortest path problems are solved by companies like FedEx or UPS who are delivering, who are doing logistics like travel websites, for planning airline routes. Shortest path problem is not just solved by Google, it's being solved in a lot of places and there are many problems which do not have anything to do with graphs, which do not have anything to do with shortest paths per se. But knowing shortest paths, you can solve them using shortest path. Like for example, playing Pac-Man, playing games like Pac-Man. If you've ever played the Pac-Man game, you have a bunch of evil characters that are trying to eat your good character and your good character is trying to eat some candy through a maze and the evil characters or trying to chase after you. The evil characters are basically going to be controlled by some form of a shortest path algorithm. If you've played, this is a classic computer game. For those of you who were not around in the days of classic arcade games, this is a classic game. Very good. At least I have given you the impression that shortest path is important. If Google maps were not important enough, then you know that companies like FedEx, UPS, travel websites. A lot of companies rely on shortest paths, even networking companies, that during routing, I want to know the shortest path from A to B. Shortest paths are important. Let's now talk about shortest path problems, a hierarchy of shortest path problems. In general, we will study two flavors of shortest path problems, single source and all pairs. What do they mean? In a single source shortest path problem, you are given a graph, you're given a directed weighted directed graph. If you are given a weighted directed graph and you're given a single source S, you are given a source vertex. Now give me the shortest paths from S to all destinations; s1, s2, s3, s4, so give me from S to all destinations? The idea here is the output of this algorithm is going to be a table. If S itself is the destination, then the cost will be zero, going from S to S is going to be zero and the path is going to be simply the empty path. If I want to go from S1, cost as one path is going to be s2, s1, if I want to go to s2, cost is 2.5. S2, S1 to s2, so I want to build up like this. For every possible destination, I want to know what the shortest path cost is and I also want to retrieve the path for you. This is called single source. If you want to know the shortest cost path from s to t, then you look it up from the table, source node s. Build a single shortest path from s and look up the cost of s to t and this allows you to go from s to t. If you change your mind, you can go from s to t2, s to t3, but if you change the source in this table, you will have to recompute a new table for the new source potentially, and this is called single source. The other problems are called all pass. Here I want to compute for all pairs of vertices, I want to compute the shortest path distance and I want to compute the shortest path itself. Now, obviously this is going to be more expensive than what? Than single-source. It's going to be way more expensive than single source, but we will look at it next week. This week we are going to look at single source. All right, very good. Now, one of the important things is what about single destination? Does that even make sense? Suppose I have a destination t, and for every possible source, I want to know the shortest path from that source to the destination. For example, suppose t is Rome knowing that all roads lead to it, it's a natural question to know what's the length of the shortest path to Rome. But interestingly enough, if you know how to solve single-source, you can easily solve single destination. How is that? Well, take your graph, just reverse the direction of all the edges. Compute the transpose graph or the reverse graph, and simply solve a single source shortest path problem on this transpose graph and you're done. Single destination is easy if you know how to solve single-source. We will mostly focus on solving single-source shortest path problems. Now I'm going to talk more about single source shortest path problems. In a single source shortest path problem, I have as an input, a weighted directed graph G with vertices V, so number of vertices is n, edges E, number of edges is m. There is a weight function. If you have an edge from u to v, that is the weight on this edge. The weight can be positive, the weight can be negative. Sometimes you can have negative weights. What's the meaning of negative weights? Depends on the problem. Of course, if weights are measuring distances, then negative weights are not going to be meaningful. On the other hand, if weights are measuring the difference between that length of the road and two kilometers, let's say, so if the road is less than two kilometers, maybe I put in a negative value, for some reason. Then let's say that's the way my problems are built. Then negative weights have a meaning there. Very good. Sometimes for example, let's say a company has built a brand new road and it's incentivizing you to take that road by giving you $10 every time you take the road and that offer is valid until October, just to get people on this new road. Well, in that case, there is an incentive given to you to take the road, and therefore, you might have negative weight edges in such a graph. If you're a logistics company and you want to represent this incentive, you might do so with a negative weight edge, because, well, every time you take that edge you are going to gain some money, so that's a negative cost. These are the inputs to the problem. Now it makes sense to think carefully about the output, I've already told you what the output looks like. Well, the output looks like this. I need a table. For every destination, S, S_1, S_2, I need a cost, the shortest path distance to that destination. Previously, I told you I need the path itself. What's the shortest path? What are the sequence of edges I need to traverse to get from S to S_1, so S to somewhere, to somewhere else to S_1. Now, I need a sequence of edges to traverse. How do I represent that? Well, I'm going to talk about this right now. First property of shortest paths is shortest paths form a tree. Let me do that with a concrete example, and then explain what I mean and prove the property. First property is shortest paths form a tree-like structure. What does that mean? Let's take an example. Here's your graph. I would like to have a source vertex of one, and I would like to know the shortest path from the vertex 1 to every other vertex in the graph. The result is going to be a table. So sources 1, and what are the destinations? I build a table for various destinations, so destination could be 1, the source itself, 2, 3, 4, 5, and 6. What's the cost of going from 1-1? That's the easiest path, 0 and the path is empty, so I'm going to write the epsilon for empty. That's going to be the simplest thing. What about 1-2? Well, this is easy. You can work it out. The shortest path from 1-2 cost is 1, and the path is go from 1-2 directly. What about from 1-3? Well, if you look at it, There's many ways of getting from 1-3, so I could go from 1-2, 2-3, the cost of that is 3. I could go from1-4, 4-3, cost of that is 4.5, 1-2, 2-4, 4-3. There's multiple ways, but if you see this, the shortest path is going to go from 1-2 for destination 3, the shortest path cost is 3, and it's going to go from 1-2, 2-3. For destination 4, the shortest path, the cost is going to be what? 1.5, and it's going to go from 1-4. For destination 5, what's going to be the cost? The cost is going to be 4, and it's going to go from 1-2, 2-3, 3-5. For destination 6, the cost is going to be 3, and it's going to go from 1-4, 4-6. Now, one thing to notice is that the path is going to be difficult to store. What can we do instead of storing this path? One thing to do is we can always record the parent. The parent is going to be the last node before the destination node. For example, the parent for five is going to be three and the parent for six is going to be four. This is always the last path one node before you reach the destination node, as I have shown by circling. If I just told this last path one node it's enough, and remember if you've already seen this in BFS and DFS, it's the concept of the parent pointer pi, and by storing the last path one node, it's easy to see. If t hat is the last path one node, then if I need to get from S to t hat, then I know how to get from S to T, and that's the important part. This is an important aspect of shortest path. I don't need to store the entire path. I just need to store the last path one node and I can recursively recover the path. Is that okay? This is an important part. We already saw some of this in breadth-first search. Now this gives us a property of shortest path. If I commit to reaching t hat and reaching T through t hat, then if I get the shortest path from S to T, it must contain the shortest path from S to t hat. The shortest path from S to T must involve shortest path from S to t hat and this is important. This is a form of something that you have seen before and this is nothing but a statement of the optimal substructure property stated in the reverse direction. Again, that's important to know. Why is this the case? Let's take some other path. Yellow path from S to t hat and let's say if that were shorter than the red path from S to t hat. Well, by concatenating the yellow path and the red edge from t hat to T, I could have gotten to T in a shorter manner. This is just a form of the optimal substructure property and that's in the reverse manner. This is the optimal substructure in the reverse direction. There is another way of stating the optimal Substructure. Suppose I start from S and I commit to going to a node s hat. Then if I want to get the shortest path from S to T, then this segment must also be the shortest path from S to t hat. That's important to note. This is the optimal substructure in the reverse sense. If I know that the last node before T is t hat, then I need to get to the shortest path from S to t hat. Likewise, if the first edge from S is to s hat, then the segment from s hat to T must be the shortest path. This is an instance of optimal substructure. Like you guessed, shortest path algorithms are going to be a form of dynamic programming on graphs. This cost table that you see here is going to be like your memo table. You don't need to store the paths. You just need to know the parents so that you can look up. The parents are giving us the option for t hat that's giving us the shortest path overall from S to T. Once we know this, how do we look up the answer? Well, if you know the parent and suppose you want to look up the path from five, well the parent of five is three. I know that the last edge on the path is three to five. What's the parent of three? Is two. I know that the edge to get to three must be through two. What's the parent of two? one, but one is the source. To get to five, I need to go one to two to three to five. This is important. All shortest path algorithms are going to build a cost table and a parent table. This is going to be important, and hopefully this is clear why we need to build both. Finally, we will talk about the effect of cycles. So far we have not really talked about cycles. What do cycles end up doing to the shortest path problem? Here's an example of a graph. I'm going to draw a graph and the edge weights are two, three, one, four. Does this cycle matter? Well, the problem with the cycle is it gives you infinitely many parts from one to four. You can take from one to two, two to three. You can take from one to two, two to five, five to four, four to two, two to three and this takes a cycle once. Now you can cycle twice. You have infinitely many possibilities in the graph but the nice thing is because the weight of the cycle is positive or is greater than or equal to zero. Even if it were at zero weight cycle, this would be true. The cycle doesn't matter. Taking the cycle only makes the paths costlier. Good. Unfortunately, if your graph has negative weight, this is no longer true. Let's take the same example, but let's make negative weights now. Now the weight of the cycle here is minus one. This is a negative weight cycle. Going around the cycle, the shortest path distance from one to two, two to three, is minus infinity. Why is that? Because I can keep going around the cycle, and I can make the weights of the path smaller and smaller. If a graph has a negative weight cycle, then shortest path distances from any source, to any destination, either you can take it to be undefined, or negative infinity. I will explain why we go for such a drastic interpretation, negative infinity. Here's the idea, suppose I have a graph, let's go back to this original graph, which is already a nice graph, and let me add a new edge from a new node one to five, and let's give it a weight too. You might say, hey, one to two is well-defined, is not well-defined, because the negative cycle comes into effect, one to three is not well-defined, one to four is not well-defined, one to five is not well-defined, but there is a shortest path from one to five, which is two. That is one interpretation. However, remember that this negative weight cycle has this following interpretation too. If an edge doesn't exist in the graph, let's say five to one doesn't exist, you can say it exists with cost infinity. This is one of the interpretations you can give. It's one interpretation. This, we will use it again and again in certain problems. You assume that there is a plus infinity weight edge from five to one, from four to three. Under this interpretation, you see, if you have a negative weight cycle, that's going to mess up the distance to five, because now you are being forced to add minus infinity to plus infinity, and the answers are undefined. It's not ideal to talk about shortest paths when you have negative weight edges. I call it the foreign taxi problem. This is very common, if you have taken taxis in foreign capitals where you are completely unaware of what's going on. The taxi driver can sometimes take you through a really [inaudible] path for a long time to your destination, charging you up a lot of money. This has happened to me in a couple of foreign capitals where I did not know the place well enough. I won't name names, but this has happened to me, and I call it the foreign taxi problem. Even though you may not be on the path to your destination, you may still end up being charged a lot of money. Negative weight cycles have that kind of a flavor. Even though this negative weight cycle does not impact five, you may interpret an infinite weight edge from five to one, plus infinity weight edge, and now, you're being forced to add minus infinity, and plus infinity, which either gives you undefined result, or gives you a really bad answer. In any case, this is not ideal, so we generally don't answer this question if your graph has a negative weight cycle. That is more of an Introduction to shortest paths. In the next lecture, I'm going to talk about the first algorithm, which is the dynamic programming algorithm, and it's called the Bellman-Ford algorithm. It's a simple algorithm. It's going to setup shortest paths as a dynamic programming problem, and solve it. Hopefully it will be an introduction to dynamic programming on graphs for you. See you in the next lecture. Bye.
