[Problem proposal] Shortest Path (Negative Edges)

[koosaga]

Problem name: Shortest Path (Negative Edges) (Optional) Problem ID: shortest_path_negative_edges

Problem

Given a weighted directed graph and a source,

• If there are negative cycles, report any negative cycle and terminate.
• Otherwise, for all $v$, print the length of shortest path or state no shortest path exists.

Constraint

$1 \le N \le 4\,000, 0 \le M \le 10\,000$ $|c_i| \le 10\,000$ Graph may contain loops and multiple edges

Solution / Reference

• Dijkstra: Incorrect
• Floyd Warshall: TLE. $O(n^3)$
• SPFA, Bellman Ford: OK. $O(nm)$
• BNW23: OK (arxiv, korean explanation). $O(m \log^3 n \log(n|w|))$

(Optional) Note / Discussion

Similar problem on Baekjoon OJ: https://www.acmicpc.net/problem/11657

Possible problem variations:

• Single source, single sink, print any negative cycle or backtrack shortest path, like https://judge.yosupo.jp/problem/shortest_path
• Single source, single sink, backtrack shortest path, only print negative cycle when backtrack is not possible. variation of above.
• Single source, all sink, do not report negative cycle manually, just state no shortest path exists. (This is WLOG with the original problem, after SCC decomposition)
• Divide into two problems (one finds negative cycle, one finds shortest path given that graph does not contain it)

Possible input variation:

• Allow loops?
• Allow multiple edges?
• $N, M$ can be reduced if BNW23 have too poor performance, but I will try to make it pass.
• Will try to make $c_i$ small in order to favor BNW23. But subject to change if I don't have good tests.

I think it can be completed only about 3 months later.

[NachiaVivias]

I have 2 questions :

(1)

Is " $|c_i| \le 10,000$ " necessary?

843 has been posted, where $N,M \leq 3000$ is preferred. How about $N,M \leq 3000$ and $|c_i| \leq 10^9$ ?

(2)

I think it can be completed only about 3 months later.

Does that mean that you are ready to do the work for this problem ?

[koosaga]

Is $|c_i| \le 10\,000$ necessary?

It could be significant for scaling, maybe. I don't want to take risks if I don't have to. For the limit, I think it's better discuss this after we have implementation.

Does that mean that you are ready to do the work for this problem ?

I'll do the work. It's great if anyone can provide help, or do it instead of me. I won't be prepared to start until the end of May.

[koosaga]

If anyone is interested, please mail me to [my github id] gmail. I will add you to the slack workspace.

[maspypy]

843 has been posted, where N,M≤3000 is preferred. How about N,M≤3000 and |ci|≤109 ?

I proposed $N,M\leq 3000$ in https://github.com/yosupo06/library-checker-problems/issues/843 . But the specific numbers are provisional and not significant.

I think $|c_i|\leq 10^9$ is more standard, but $|c_i| \leq 10^4$ is also good if many solutions can be verifyed by doing so.

[maspypy]

We need to treat loops correctly if edge weights can be negative, so it is good to include loops. Other things can be same as https://judge.yosupo.jp/problem/shortest_path. ($s\neq t$, allow no multiple edges)

[noshi91]

Problem name should be 'Shortest Walk' rather than 'Shortest Path'. The shortest walk of an undirected graph containing negative edges is obvious, so there is no need to specify that the graph is directed.

[maspypy]

@koosaga How is the progress going? Is there any trouble?

[koosaga]

@maspypy

I finished the preparation in Polygon. Final limitations are $2 \le N \le 20\,000, 1 \le M \le 20\,000, |c_i| \le 10\,000$. I implemented two solution: Bellman-Ford $O(nm)$, and Goldberg's Scaling algo $O(m \sqrt n \log C)$. BF runs in 2.1s and Goldberg (Scaling) runs in 0.6s, but maybe tests are not strong enough against Scaling.

I will attach the polygon package below. It would be great if you could port this into the library-checker format, as I'm not familiar with the format here (and someone need to write a Japanese description anyway).

https://www.dropbox.com/scl/fi/cpd4qton3gw7awo8z0jyt/shortest-path-negative-edges-10-linux.zip?rlkey=nmqc5sl87k0zfi2z4tot0ldvz&dl=0