<p>Yes there is no reason to add the extra vertex <span class="math-container">$v_0$</span> 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 <span class="math-container">$v_0$</span> if the graph was not fully connected so it is a more general answer.</p>

CC BY-SA 4.0
2018-12-03T15:56:16.827Z
2018-12-03T15:56:16.827Z
Sandeep Silwal
<p>I am studying applications of shortest path, in particular arbitrage.</p>

<p>Specifically, I was reading these two resources:
<a href="https://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage">https://stackoverflow.com/questions/2282427/interesting-problem-currency-arbitrage</a>
<a href="http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf" rel="nofollow noreferrer">http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf</a></p>

<p>I do not understand when and why it is necessary to add an additional vertex to the graph in order to solve this problem.<br>
In the solution outlined in <a href="http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf" rel="nofollow noreferrer">here</a>, halfway down page 7 it says "This method works because adding the new vertex ensures that all negative weight cycles are reachable..."</p>

<p>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.  </p>

<p>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.</p>

CC BY-SA 4.0
2018-12-02T21:02:59.813Z
Why the downvotes?
Hunle
<graph-algorithms><shortest-path>
When is extra vertex required in arbitrage detection using Bellman Ford?
Hunle
# When is extra vertex required in arbitrage detection using Bellman Ford?

(Asked by: username_0 on 2018-12-02)

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](http://courses.csail.mit.edu/6.046/spring04/handouts/ps7sol.pdf), 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.

**Tags:** graph-algorithms, shortest-path

> **Comments:**
> **username_0**: Why the downvotes?  

---

## 1 answers

### Answer by username_1 on 2018-12-03. Score: 1

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.


---

