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 with constraints in the form , compute a feasible solution.
Resources
Resources | |||
---|---|---|---|
MIT | Linear Programming Trick |
Problems
Timeline (USACO Camp):
- equivalent to Timeline (Gold) except and negative values of are possible.
Floyd-Warshall
Focus Problem – read through this problem before continuing!
Solution - APSP
C++
const int MOD = 1000000007;const ll INF = 1e18;int n,m,q;ll dist[150][150], bad[150][150];void solve() {F0R(i,n) F0R(j,n) dist[i][j] = INF, bad[i][j] = 0;F0R(i,n) dist[i][i] = 0;F0R(i,m) {
Problems
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.
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!
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!
Give Us Feedback on Shortest Paths with Negative Edge Weights!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.