EE363, Winter 2001-2002 1Analysis of the Minimum Cost Path Problem and theBellman-Ford AlgorithmJun SunJanuary 31, 2002Let us describe the problem. We are given n nodes, labeled 1,...,n, and a set of costsCij, i, j =1,...,n, which represent the cost of moving from node i to node j. (Note thatthis is the transpose of the cost matrix C defined in homework 1 problem 3.) If there is nolink from node i to node j, i.e., if transitions from node i to node j are not allowed, we takeCij= ∞. Note that we are not assuming Cij≥ 0, and generally, Cij6= Cji.Apath fromnode i to node j consists of a finite sequence of nodes which begins from node i and ends atnode j: i = i0,i1,...,im−1,im=j.Thelength of the path is the number of links it contains.In the above case, the length of the path is m. The total cost for the path is given by thesum of the costs along the links:Pm−1k=0Cikik+1.The problem is to find the minimum cost path, of any length, from some beginning nodeto some destination node. We’ll assume that the destination node is 1, and we set C1j= ∞for every node j in our following discussions. (Actually these costs don’t appear in theequations at all, so it doesn’t really matter.)A cycle is simply a path that has the same beginning and ending node. In our problem,we assume that every cycle has nonnegative cost. This assumption guarantees the existenceof the minimum cost path from every node i to node 1. (Note that we haven’t proved it yet,but we will give a similar proof in Lemma 2.)We denote the cost of the minimum cost path from node i to be V∗i,i =1,...,n.Werefer to V∗as the min-cost vector. From the DP principle, these minimum-cost-to-go satisfyV1=0,Vi=minj(Cij+ Vj),i=2,...,n, (1)which is Bellman’s equation. In general, there can be many solutions of Bellman’s equation.But as we will show in the following proposition, none of them will exceed V∗i.Proposition 1 Let Vi,i=1,...,n satisfy Bellman’s equation. Then Vi≤ V∗i, i =1,...,n.Proof It is trivial if i = 1. Assume i 6= 1. Take the minimum cost path from node i tonode 1: i = i0,i1,...,im−1,im=1. ThenV∗i=Pm−1k=0Cikik+1. From Bellman’s equation, wehave Vi≤ Cij+Vjfor j =1,...,n. Therefore, (Vi0≤ Ci0i1+Vi1),...,(Vim−1≤Cim−1im+V1).Combining these inequalities gives Vi0≤ Ci0i1+ ···+Cim−1im+V1=V∗i,sinceV1=0.The following proposition tells us when the solution is unique.Proposition 2 If every cycle has positive cost, then the only solution to Bellman’s equationis V∗, the min-cost vector.Proof Suppose V is also a solution to Bellman’s equation. By Proposition 1, showingVi≥ V∗ifor every i implies V = V∗. Bellman’s equation tells us that for every i 6=1,wecan always find an i0(not necessarily unique) such that Vi= Cii0+ Vi0. We look only at thedirected arcs between nodes i and i0for i =2,...,n. Every node, except node 1, has anoutgoing arc. Suppose we begin from any node i 6= 1 and follow these arcs. After n − 1stepswe are either at node 1 or at a node that we had previously visited. If we reach a node j thatwe had previously visited, then a cycle formed during the course. Since the cost-to-go Vjisthe same at the end of the cycle as it had been at the beginning, we conclude that no cost hasbeen accumulated in this cycle, contradicting our assumption. Suppose instead that this pathreaches node 1: i = i0,i1,...,il−1,il=1. InthiscaseVi=Pl−1k=0Cikik+1+ V1=Pl−1k=0Cikik+1.Since this is a path from node i to node 1, its cost should be no less than V∗i, i.e., we haveVi≥ V∗i.We assume that every cycle has positive cost from now on.One way to solve Bellman’s equation is the iterative method:Vt+1i=minj(Cij+ Vtj),i6=1,Vt+11=0,which is known as the Bellman-Ford algorithm. We will show that the iteration convergesto V∗for an arbitrary initial vector V0with V01=0.For nodes i 6=1andj6= 1, define Wtij= minimum path cost over all paths from i to jwith length t;andWti1= minimum path cost over all paths from i to1withlength≤t.Wecan establish the following two lemmas:Lemma 1 Vti=minj(Wtij+ V0j), for any i 6=1andt≥1.Proof Use induction. It is trivial when t = 1. Assume that it holds for some t ≥ 1. Forany nodes i 6=1andj, let us denote by Ptijthe set of paths appearing in the definitions ofWtij.Thenminj(Wt+1ij+ V0j)= min(i,i1,...,im,j)∈Pt+1ijj=1,...,n(Cii1+ ···+Cimj+V0j)=min(Ci1,mini16=1(Cii1+min(i1,i2,...,im,j)∈Pti1jj=1,...,n(Ci1i2+ ···+Cimj+V0j)))=min(Ci1,mini16=1(Cii1+minj(Wti1j+V0j)))=min(Ci1,mini16=1(Cii1+ Vti1))=mini1(Cii1+ Vti1)= Vt+1i2Lemma 2 Wti1= V∗i< ∞ for all nodes i 6=1andt≥n−1. Wtij→∞as t →∞for allnodes i 6=1andj6=1.Proof The first one is pretty simple. By the definitions, we have V∗i≤ Wti1for any t.Trivially, the minimum path from i to 1 has length ≤ n − 1, i.e. , Wti1≤ V∗ifor t ≥ n − 1.The second one is also simple intuitively, and here we provide a rigorous argument.We say a cycle is simple if it does not contain any other cycles. It is clear that the costof any cycle will be greater than or equal to cost of a simple cycle it contains. Hence if wedefine  as the minimum cost of all cycles in the graph, indeed we only need to consider allsimple cycles, the number of which is finite. Then >0. Similarly, we say a path is simpleif it does not contain any cycles. By the same arguments, if we want to find the minimumcost of all paths in the graph, say K, we only need to consider all simple paths and simplecycles, the number of which is finite. Then K>−∞.Now consider any path of length t. At least one node should appear in the sequence noless thant+1ntimes, hence the path contains at least (t+1n− 1) cycles. Then its cost is always≥ (t+1n− 1) + K. Therefore, for nodes i, j 6=1,Wtij≥ (t+1n− 1) + K.ThenWtij→∞ast →∞.Proposition 3 The Bellman-Ford algorithm terminates after some finite number k ofiterations, with Vki= V∗ifor all i =1,...,n, for an arbitrary initial vector V0iwith V01=0.Proof Lemma 1 tells us that Vti=minj(Wtij+ V0j), for i 6= 1. By Lemma 2, ∃k ≥ n − 1,such that for any j 6=1andt≥k,wehaveWtij+ V0j>V∗i=Wti1=Wti1+V01,i.e., Vti= V∗i.One possible set of initial conditions in the Bellman-Ford algorithm is V0i= ∞ for i 6=1and V01= 0; this is the choice most often discussed in literature. As a trivial corollary ofLemma 1, one can show that the algorithm terminates after at most n − 1 iterations. Indeed,in the absence of additional information, it is a good choice.