PDF of Eric’s handwritten notes are here.

**Shortest path algorithms using DP**

Input: Directed with edge weights .

Fix : Dijkstra’s algorithm finds for all , length of shortest path from to in time , assuming all edge weights are positive.

What if negative weight edges? May be negative weight cycles (see example in handwritten notes). Assume no negative weight cycles for now (see how to deal with them later.)

Solve using DP. **Note**: for shortest path from to , visits every vertex at most once if no negative weight cycle.So is of length edges.

DP idea: use edges on the path.

For , and ,

let length of shortest path from to using edges.

**Base case:** ,

and for : .

**For** : look at a shortest path from to using edges.

Thus, .

**Pseudocode:**

:

- for all ,
- for
- for all
- for all :
- if , then

- Return

Running time: .

How to find a negative weight cycle?

Check if for some .

Now what if we want all-pairs shortest paths? Then if we run Bellman-Ford times, we get a time algorithm.

**Better approach:** using dynamic programming.

Let length of shortest path from to .

Do we condition on the number of edges as in Bellman-Ford? This will give an time algorithm), is there a better approach?

Instead we will condition on the set of intermediate vertices.

**Idea:** Arbitrarily order the vertices, so .

For and ,

let length of shortest path from to using a subset of as intermediate vertices.

**Base case: **

**Recurrence:** look at for : (assuming no negative weight cycle)

- if is not used, then
- if is used, then the path goes through and so it can be broken into two parts: a path from to and to (see the handwritten notes for an illustration).

Hence, for and vertices :

.

**Pseudocode:**

:

- For all :
- for all :
- if ,
- then
- else

- if ,

- for all :
- For
- for all
- for all

- for all

- for all
- Return

Running time is .

How do we check for a negative-weight cycle?

Check if for some .