# Shortest Paths with Negative Edge Weights

Authors: Benjamin Qi, Andi Qu

### Prerequisites

Returning to Bellman-Ford and Floyd-Warshall.

## Bellman-Ford

Resources | |||
---|---|---|---|

cp-algo | |||

cp-algo | with Bellman-Ford | ||

CP2 |

### Shortest Paths

Focus Problem – read through this problem before continuing!

#### Solution

### This section is not complete.

### Finding Negative Cycles

Focus Problem – read through this problem before continuing!

#### Solution

### This section is not complete.

### Simple Linear Programming

You can also use shortest path algorithms to solve the following problem (a very simple linear program).

Given variables $x_1,x_2,\ldots,x_N$ with constraints in the form $x_i-x_j\ge c$, compute a feasible solution.

#### Resources

Resources | |||
---|---|---|---|

MIT | Linear Programming Trick |

#### Problems

Timeline (USACO Camp):

- equivalent to Timeline (Gold) except $N,C\le 5000$ and negative values of $x$ are possible.

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

RMI | Normal | Show Sketch |

## Floyd-Warshall

Focus Problem – read through this problem before continuing!

### Solution - APSP

C++

1const int MOD = 1000000007;2const ll INF = 1e18;34int n,m,q;5ll dist[150][150], bad[150][150];67void solve() {8 F0R(i,n) F0R(j,n) dist[i][j] = INF, bad[i][j] = 0;9 F0R(i,n) dist[i][i] = 0;10 F0R(i,m) {

### Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

APIO | Hard | ## Show TagsAPSP, Binary Search |

## Modified Dijkstra

The Dijkstra code presented earlier will still give correct results if there are no negative cycles. However, the same running time bound no longer applies, as demonstrated by subtasks 1-6 of the following problem.

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

APIO | Hard | ## Show TagsSP, Output-only |

This problem forces you to analyze the inner workings of the three shortest-path algorithms we presented here. It also teaches you about how problemsetters could create hack cases!