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.

  • 1
    Why the downvotes? – Hunle Dec 2 at 21:02

Yes there is no reason to add the extra vertex $v_0$ since the graph is fully connected and every vertex is reachable from every other vertex (the table specified in the problem seems to be a complete table). Since the graph is fully connected, if there is a negative weight cycle, we can find it by starting from any vertex. However, you would need the vertex $v_0$ if the graph was not fully connected so it is a more general answer.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.