this question is a follow-up to Detecting Negative Cycles in Undirected Graphs.
When checking publications related to the problem of detecting negative cycles in weighted, undirected graphs (the apparently newest one being this one ), I saw only $b$-matching and $T$-joins being mentioned and investigated as methods for that problem.
Question:
Are there concrete examples of undirected, weighted graphs, that contain negative-cost cycles, wich the Bellman-Ford algorithm fails to detect, resp. can the existence of such graphs be proven?
Best Answer
If an undirected graph has a negative weight cycle, then the Bellman-Ford algorithm will detect it. However, if an undirected graph does not have a negative weight cycle the Bellman-Ford algorithm may still detect one. So, the answer to your specific question in the body is no (there are no false negatives) while the answer to the general question is yes (there may be false positives). In fact Bellman-Ford can only really be used with nonnegative weights for undirected graphs.
The Bellman-Ford algorithm works on directed graphs. To make it work with undirected graphs we must make each undirected edge into two directed edges (one in each direction) with the same weights as the original undirected edge. Now any negative weight undirected cycle is transformed into a negative weight directed cycle, and hence would be detected. In any negative weight edge is transformed in a negative weight cycle of length two! Thus Bellman-Ford will always detect a negative cycle if there is any negative weight edge.