title: How to find the path for the most negatively-weighted cycle which goes through a specific source node?
body: <p>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.</p>
  
  <p>I have studied an application/ extension of the Bellman-Ford algorithm (henceforth referred to as the "Huang algorithm") found <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.1981&amp;rep=rep1&amp;type=pdf" rel="nofollow noreferrer">here</a> 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.</p>
  
  <p>Here is my current research into this topic:</p>
  
  <p>On the n<sup>th</sup> 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. </p>
  
  <p>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)</p>