Contact Form Submission - Other (Problem Solution - APSP (with negative weights) (ID: kattis-allpairspath))

[maggieliu05]

Someone submitted the contact form!

URL: https://usaco.guide/problems/kattis-allpairspath/user-solutions
Module: Problem Solution - APSP (with negative weights) (ID: kattis-allpairspath)
Topic: Other
Message:
A question.

In this paper:
Stefan Hougardy (April 2010). "The Floyd–Warshall algorithm on graphs with negative cycles". Information Processing Letters. 110 (8–9): 279–281. doi:10.1016/j.ipl.2010.02.001.

It says that:
We have shown that during the execution of the Floyd–
Warshall algorithm exponentially large numbers may occur, if the input graph contains negative cycles. Theorem 2
implies that even for graphs with less than 30 vertices and
60 edges with weight −1 it may happen that during the
execution of the Floyd–Warshall algorithm numbers with
absolute value larger than 2^64 occur. This shows that for
larger graphs it can be quite likely to have subgraphs causing an overflow.
Of course, there is a simple way to avoid this pitfall:
Instead of checking for negative cycles at the end of the
algorithm one can include lines 8 and 9 in Fig. 1 in the forloop in line 6 without increasing the worst-case runtime.
Another possibility is to first use the Bellman–Ford algorithm [8] to detect negative cycles in O(mn) and to start
the Floyd–Warshall algorithm only if the input graph has
no negative cycles. Most implementations of the Floyd–
Warshall algorithm we have seen apply neither of these
two solutions and therefore might fail if negative cycles
exist in the input graph. With this note we want to make
aware of this potential pitfall.

So, do we need to add some lines in the usual Floyd algorithm to prevent overflow from happening? I'm not sure on how to construct a counter-example, sorry.

[bqi343]

I agree, the same applies to some of the other module solutions. Though I haven't really thought about how to construct counterexamples.