19
Sep

Shortest path: properties of the algorithm


The shortest path algorithm calculates labels that verify the optimality conditions of the shortest path problem. In this video, we review several properties of this algorithm. Let’s first review the ingredients of this algorithm. All the arcs on the network are associated with a cost, c_ij. All the nodes are associated with a label, lambda_i. And the algorithm is maintaining a set of nodes, that we call capital S. In the beginning, all the labels are initialized to plus infinity, except the one at the origin o, which is initialized to zero. And the set of nodes S is initialized with this origin node o. At each iteration, we choose a node i in S, and we consider all the arcs leaving i. If the optimality condition is not verified, we update the label. We check if it is consistent with the lower bound. If not, we can stop. There is no shortest path. If so, we update the set of nodes S by including node j, because its label has been updated. Once all the arcs leaving i have been treated, we can remove node i from the set S. And we will stop these iterations as soon as S is empty. We first derive properties that are valid at the end of each iteration. The first one says that if a node is in the set S, then its label is not equal to infinity. We can prove this result by induction. This is true after initialization. Indeed, at initialization, there is only one node in S, and we know that its label is 0, so it’s not infinity. Let’s assume now that the property is true at the beginning of the iteration. It means that, when we treat node i, its label is a finite number. Each other nodes that will be included in S during that iteration, before we do that, we will update its label. And the value that we will give to the label will be the sum of lambda_i, which is a finite number, and the cost, which is also a finite number. Therefore, at the end of the iteration, all the nodes that will be in S will have a label which is not infinity. The second property that is true at the end of each iteration of the algorithm is the following. For each node i, the value of its label does not increase during the iteration. Actually, this is a direct consequence of the update condition. Indeed, the only possibility for a label to be updated is because its value was greater, was strictly greater than lambda_i plus c_ij. It means that its value will decrease during that iteration, which proves the result. We now want to show that, at the end of each iteration, every label which is not infinity, represents the length of one path from the origin node o to the node i. And we will show it using induction. The first stage of the algorithm is the initialization. After initialization, only one node has a label which is not infinity. This is node o. And the label that we associate with node o is zero. Actually, zero can be interpreted as the length of a path from o to o. Which has length zero, because we stay at the same node. So this interpretation is valid in the beginning. Now, let’s look at the first iteration of the algorithm. The first iteration starts from node o, and considers all the arcs that are leaving the node. They have a cost, let’s say… c_o1, c_o2, c_o3. We have node 1, node 2, and node 3. During the first iteration, the labels of these nodes will be updated to the label of node o which is zero, plus the cost of the arc. Which will be equal to the cost of the arc. For node 2, the new label will be the cost of the second arc. And node 3, the label will be the cost of the third arc. After the first iteration, the label of the nodes, at least the label of the nodes which have a non infinity value, are exactly the length, or the cost, of the arc, which can be interpreted as the length of one path between node o and node 1, or node o and node 2. It’s a path with only one arc. So after the first iteration, this can be interpreted as the length of a path. Now let’s work by induction. Let’s suppose that this property is true before we treat node k. And let’s show that it will be again valid after the treatment of node k. So because we treat node k, it means that k is in S. So, it means that, as we have seen before, lambda_k is not infinity. It means also that from the assumption of the induction, because it is not infinity, lambda_k represents the length of one path from o to k. This is the induction assumption. And now, during this iteration, what we will do is to add one arc to the path, as we have seen before. It means that the new label that we will obtain here, will be lambda_k will be lambda_k, so the label of node k, plus the cost of the arc (k,i). and this lambda_i now can be interpreted as the length of a path. Indeed, it’s lambda_k, which is the length of a path from node o to node k, plus the length of this arc. So, the total of the two is the length of a path which starts from o and reaches node i. And the result is proved. The last thing we would like to show is that, at the end of each iteration, when a node i is not in the set S, then either its label is plus infinity, or this inequality here is verified. Actually, there are two reasons not to be in S. The first reason is that the algorithm has never reached node i yet. In this case, obviously, node i has the label that was set at the initialization phase. So plus infinity. So this is the first case. i is not in S because it has never been treated, and the label has not been updated. Now the second case is more important. It’s the case where i has been treated. So, a label has been assigned to i. And then it has been removed from S just after the treatment. By design, the algorithm is such that, after a node is treated, this inequality is verified. Just after the treatment, this inequality is verified. Now, during the iteration, we know that lambda_i, because it is not in S, will not be updated. The only possible modification in this inequation should be lambda_j. Indeed, if j happens to be in S, its label may potentially be updated. But as we have seen before, in a previous property, during these iterations, a label can only decrease. It means that if lambda_j is modified, it will only become smaller. And, therefore, this inequality will remain valid. And our result holds. We now investigate properties that are valid at the end of the algorithm, when the algorithm has finished. And the first of these properties is about the number of iterations, that can be performed by the algorithm. The next property says that the algorithm will stop after a finite number of iterations. We have two stopping criteria. A first one is… is not written on the slide. It’s: stop if the set of node is empty. And the second one is that we will stop if one label is below the lower bound on the length of simple paths in the network. To prove the result, we will assume that the termination criterion S being empty is never verified. And we will try to show a contradiction. In that case, because we remove one node at each iteration, it means that some nodes are added an infinite number of times in the set. But we know that when they are inserted in S, it means that they have been treated. So it means that the label of the node is strictly decreased. And because this happens an infinite number of time, the label of these nodes are going to minus infinity. This is not possible because we have the second stopping criterion. So if indeed, lambda_i goes to minus infinity. At some point, it will be below the lower bound, and the algorithm will stop. Which shows that it will finish after a finite number of iterations. The second property that is true at the end of the algorithm is that, if we terminate with an empty set of nodes, it means that the algorithm does not terminate because the problem is not bounded, if some of the labels are still at infinity, it means that there is no path from the origin to the associated nodes. So let’s first prove the sufficient condition, which says that if lambda_j is equal to plus infinity, then there is no path from o to j. And we’ll do it by contradiction. Suppose that there is a path from o to… to j, then mechanically, the algorithm will assign labels to each of the nodes in the path. So it will start with a zero here, and plus infinity everywhere. Because o is in the set, this arc will be treated, and the label will be updated to a finite number. This will not be infinity any more. And because the label has been updated, it will be inserted in the set S. It means that the algorithm will, at some point, treat that node. And it will have to treat that arc, and update this one to a finite number. And so on, all the way to j. So at some point the label of j will be set to a finite number. And this contradicts the assumption here. Let’s prove now the necessary condition which says that there is no path from o to j, then lambda_j equals to plus infinity. Well, actually, this is the contrapositive of the previous condition. So the contrapositive of this is that if lambda_j is different from infinity, then there exists a path from o to j. And this, we have shown before, is that, if lambda_j is a finite number, it is the length of a path from o to j. So this is verified as well. The next property says that, if the algorithm terminates with an empty set of nodes, then the label of the origin node is equal to 0. The value of lambda o is initialized to zero. And we know that, during the iterations, the label cannot increase. So we have that lambda_o must be less or equal to zero, because the only thing that a label can do is to decrease. Now let’s assume that lambda_o is strictly negative. But in that case, we have seen that, if a node has a label which is not infinity, it is the length of a path from the origin to that node. So it means that, here, we have a cycle, that is a path from o to o, of negative length. But that’s not possible, because if we have a cycle with negative length, then the algorithm will stop with this condition, and the set of nodes will not be empty. So this is not possible. At the end of the algorithm, the label of the origin node will still be zero. We have seen that, at the end of each iteration, the label of a node can be interpreted as the length of a path from the origin to the node. Again, if the algorithm has terminated with the empty set of nodes, the labels of the nodes are the length of the shortest path between the origin and the node. This is what we will show now. Consider a node ell. We know that lambda_ell is the length of a path from the origin to ell. Let’s call this path P_ell. This path starts from the origin, then follows some nodes, and reaches node ell. The length of the path P_ell is lambda_ell. Now, let’s take another path Q from the origin to a sequence of nodes to ell as well. What is the length of this path? It’s the sum of the costs of all the arcs along the path. And we know that, for each arc, because there is no node in the set of node anymore, they verify the inequality of the optimality condition. So we know that this will be greater or equal to lambda_j_1 minus lambda_o plus lambda_j_2 minus lambda_j_1 plus lambda_ell minus lambda_j_k. And, again, for each node which is not the origin or node ell, the labels will cancel out. Moreover, we know that this here is equal to zero. So the cost of Q is greater or equal to lambda_ell. And lambda_ell is the cost of P_ell. We have shown that the cost of P_ell is the lowest possible one. So P_ell is a shortest path from o to ell. The next property says that, if the algorithm terminates with an empty set of nodes, for each node in the network which is not the origin and a node that has a finite label, we have that lambda_j can be calculated as the minimum of all arcs reaching j, of lambda_i plus c_ij. The value of lambda_j can be calculated by calculating lambda_i plus c_ij for each of the incoming arcs, and taking the smallest value. We have seen in the previous property that the labels, at the end of the algorithm, can be interpreted as the length of the shortest path from origin o to each of the nodes. It means that these labels must verify the optimality conditions. The first condition here guarantees that lambda_j will be less or equal to the minimum of lambda_i plus c_ij. Because it’s less or equal to each of them. But can it be strictly lower than this value? No, because we know that there is one arc, the one that belongs to the shortest path, where the equality will be verified. So this will be an equality. This formula is actually quite important. It’s called “Bellman’s equation”. And it says that if we look at all the incoming arcs of a node, and that we calculate lambda_i plus c_ij for all these arcs. If we select the smallest value, it will correspond to the arc that belongs to the shortest path. Therefore, Bellman’s equation can be used to reconstruct the path from the labels. Let’s try to do this. We can actually use Bellman’s equation to build a subnetwork, that I will call “Bellman’s subnetwork”. So let’s take our original network which is composed of m nodes and n arcs. And assume that each cycle, if any, has positive length. Now, we need to build a subnetwork. And we do it in the following way. For each node which is not the origin, we select one incoming arc that verifies Bellman’s equation. For example, if we look at this node with label six, there are two incoming arcs. For this one we have one plus eight which is nine. Which is not equal to six. So it’s not a candidate. Five plus one equal six. So this is the one we need to include. All the arcs that have been selected in that way form a subnetwork. Because the original network has m nodes, the subnetwork will contain m minus one arcs, because we have done this for each node which is not the origin. Now the point that I am trying to make here is that this subnetwork that I am building, the Bellman’s subnetwork, is actually a tree. I have already shown that it has m-1 arcs. So the last thing I have to show is that it contains no cycle. So let’s assume that this Bellman’s subnetwork contains a cycle. So… I don’t know.. there is a cycle from i_1, i_2, i_3, i_ell, and then it goes back to i_1. The length of this cycle is the sum of the costs. So c(i_1,i_2) plus c(i_2,i_3) plus… all the way to c(i_ell,i_1). Because all these arcs are in the Bellman’s subnetwork, they verify Bellman’s equation. And, therefore, the costs are equal to the difference of the labels. As we have seen in previous proofs, the labels of the intermediary nodes will cancel out. lambda_i_2, lambda_i_2, lambda_i_3 with lambda_i_3 and so on… All the way to lambda_i_ell. But in this case, because we have a cycle, the labels of node 1 here will also cancel out. So the length of this cycle is zero. But we have assumed before that each cycle in the network has a positive length. So this cannot be true. It shows that Bellman’s subnetwork, that we have built using Bellman’s equation, and that is represented on this picture, is actually a tree. Because it is a tree, it means that there is exactly one path between the origin o and any node i. And because that path belongs the Bellman’s subnetwork, it verifies the optimality conditions, it is the shortest path. So we call Bellman’s subnetwork “shortest path tree”. It gives you all the shortest paths from the origin to each node. In this video, we have reviewed several properties of the shortest path algorithm. In particular, we have seen that the labels can be interpreted as the length of a path from the origin to a node during the iterations. And, at the end of the algorithm, it’s actually the length of the shortest path between the origin and the node. We have also seen how Bellman’s equation can be used to build the Bellman’s subnetwork, which happens to be a spanning tree. This is the shortest path tree.

Tags: , , ,

There are no comments yet

Why not be the first

Leave a Reply

Your email address will not be published. Required fields are marked *