I am trying to find the path for the most negative cycle in a graph G which starts and ends at a specified source node S.
I have studied an application/ extension of the Bellman-Ford algorithm (henceforth referred to as the "Huang algorithm") found here which describes how to find a negative cycle reachable from a specified node. However, this does not ensure that the "full cycle" going from S -> cycle -> S is negative.
Here is my current research into this topic:
On the nth iteration of the Bellman Ford algorithm, if an edge can be relaxed, then the graph contains a negative cycle. Using the Huang algorithm I can retrace the path of the negative cycle through the predecessor dictionary until a vertex repeats. When a vertex repeats, I cease iterating over the predecessor and now have my path for the negative cycle. However, the source vertex is often not in this path. I believe it is also sometimes not the most negatively-weighted path.
I would like to find the most negative cycle of which S is a part. (This can include a cycle with a subcycle detected by the Huang algorithm)