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.