• We looked at the shortest path problem where we obtain the shortest path from every s to by inputting a graph of G=(V,E) and all edges have a ce of any weight (positive/negative).
  • Dynamic programming was used to solve the problem.  There are 3 basic rules of thumb:

*There are many sub-problems

*Optimal solutions can be computed from solutions with sub-problem

*For each problem, there is a total ordering that gives way for an iterative solution.

  • We also defined a recurrence relation with OPT(i,u) = cost of the shortest path from u to t with at most I edges.  The full relation is: 


The column i in the problem ONLY depends on the previous column (i-1).

We have a matrix M[u,i] which should correspond with the OPT(i,u).  This can be proven by induction.  The Bellman-Ford algorithm is as follows:

To figure out the length cost of shortest s-t path when given the matrix M, we will need to obtain the matrix M[s, n-1].  See the below for an example.

The correctness of the algorithm can be proved by induction, as previously mentioned above.  The running time of the algorithm is O(mn).   Based on the analysis, the for loops generate a run time of O(n3).  This includes the first statement for setting up the matrix.  Combined with the sum of all the matrix operations in the M[u,i] statement, we get a final running time of O(nm).

If we have an algorithm to reconstruct shortest path, we can reduce the space from O(n2).  An observation is that the ith column only depends on the (i-1)th column.

Read Section 6.8 in book


Given graph G, is there a simple path of length n-1?  One way to do this is to invert the problem, but you could run into a negative path cycle.  The end edge weights can also be negative.  There are two things to look at when approaching the problem:

  • *In the shortest path problem, it can be solved by a polynomial time algorithm.
  • *Is there a longest path of length n-1?  If you are given a path that can be verified in polynomial time, then there is a path.  This can be seen like a “witness”.

So is there a polynomial time algorithm for longest path?  Not really, but there is a contest regarding this scenario called (P vs. NP).  According the the problem, P and NP are defined as follows:

  • P – collection of problems that can be solved polynomially
  • NP – collection of problems that have a polynomial-time verifiable witness to the optimal solution

If P was equal to NP, then there would be a way to solve a problem P in some sort of algorithm.  There is also an alternate definition to NP where you can “guess” a witness and if correct, you can verify it.

Proving this algorithm based on both scenarios is not possible at this moment.  To prove that P = NP, you can pick any one problem in NP and show that it cannot be solved in polynomial time.  However, all known proof techniques currently will not prove that.  Proving P=NP on the other hand will make cryptography collapse as you will end up verifying your own encryption key.  You will instead need to prove that all problems in NP can be solved by polynomial-time algorithms.

Welcome to After you read this, you should delete and write your own post, with a new title above. Or hit Add New on the left (of the admin dashboard) to start a fresh post.

Here are some suggestions for your first post.

  1. You can find new ideas for what to blog about by reading the Daily Post.
  2. Add PressThis to your browser. It creates a new blog post for you about any interesting  page you read on the web.
  3. Make some changes to this page, and then hit preview on the right. You can always preview any post or edit it before you share it to the world.