PrevNext
Has Not Appeared
 0/6

Shortest Paths with Negative Edge Weights

Authors: Benjamin Qi, Andi Qu

Returning to Bellman-Ford and Floyd-Warshall.

Bellman-Ford

Shortest Paths

Focus Problem – read through this problem before continuing!

Solution

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Finding Negative Cycles

Focus Problem – read through this problem before continuing!

Solution

This section is not complete.

Feel free to file a request to complete this using the "Contact Us" button.

Simple Linear Programming

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

Given variables x1,x2,,xNx_1,x_2,\ldots,x_N with constraints in the form xixjcx_i-x_j\ge c, compute a feasible solution.

Resources

Resources
MITLinear Programming Trick

Problems

Timeline (USACO Camp):

  • equivalent to Timeline (Gold) except N,C5000N,C\le 5000 and negative values of xx are possible.
StatusSourceProblem NameDifficultyTagsSolution
RMINormalShow Sketch

Floyd-Warshall

Focus Problem – read through this problem before continuing!

Solution - APSP

C++

1const int MOD = 1000000007;
2const ll INF = 1e18;
3
4int n,m,q;
5ll dist[150][150], bad[150][150];
6
7void 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

StatusSourceProblem NameDifficultyTagsSolution
APIOHard
Show Tags

APSP, 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.

StatusSourceProblem NameDifficultyTagsSolution
APIOHard
Show Tags

SP, 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!

Module Progress:

Give Us Feedback on Shortest Paths with Negative Edge Weights!

PrevNext