I am studying applications of shortest path, in particular arbitrage.
Specifically, I was reading these two resources: https://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf
I do not understand when and why it is necessary to add an additional vertex to the graph in order to solve this problem.
In the solution outlined in here, halfway down page 7 it says "This method works because adding the new vertex ensures that all negative weight cycles are reachable..."
However, in most of the arbitrage problems I've seen, the graphs representing them are complete (fully-connected), so I cannot think of why this extra vertex is necessary.
When is it necessary to add this extra vertex and why? The best answer I can think of is when for some reason you cannot exchange a certain currency for another currency.