Question

Shortest path algorithms can be applied in currency trading. Let ${\mathit{c}}_{\mathbf{1}}\mathbf{,}{\mathit{c}}_{\mathbf{2}}\mathbf{,}{\mathit{c}}_{\mathbf{n}}$ be various currencies; for instance, ${\mathit{c}}_1$might be dollars, ${\mathit{c}}_{\mathbf{2}}$pounds, and ${\mathit{c}}_{\mathbf{3}}$ lire.

For any two currencies ${\mathit{c}}_{\mathbf{i}}$ and ${\mathit{c}}_{\mathit{j}}$ , there is an exchange rate ${\mathit{\tau }}_{\mathbf{i}\mathbf{,}\mathbf{j}}$; this means that you can purchase ${\mathit{\tau }}_{\mathbf{i}\mathbf{,}\mathbf{j}}$ units of currency ${\mathit{c}}_{\mathbf{j}}$ in exchange for one unit of ${\mathit{c}}_{\mathbf{j}}$. These exchange rates satisfy the condition that ${\mathit{r}}_{\mathbf{i}\mathbf{j}}\mathbf{.}{\mathit{r}}_{\mathbf{j}\mathbf{i}}\mathbf{<}\mathbf{1}$ so that if you start with a unit of currency ${\mathit{c}}_{\mathbf{j}}$, change it into currency and then convert back to currency localid="1658917254028" ${\mathit{c}}_{\mathbf{i}}$, you end up with less than one unit of currency ${\mathit{c}}_{\mathbf{i}}$ (the difference is the cost of the transaction).

a. Give an efficient algorithm for the following problem: Given a set of exchange rates ${\mathit{r}}_{\mathbf{i}\mathbf{j}}$ , and two currencies s and t , find the most advantageous sequence of currency exchanges for converting currency into currency . Toward this goal, you should represent the currencies and rates by a graph whose edge lengths are real numbers.

The exchange rates are updated frequently, rejecting the demand and supply of the various currencies. Occasionally the exchange rates satisfy the following property: there is a sequence of currencies ${\mathit{c}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{c}}_{\mathbf{i}\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{c}}_{\mathbf{i}\mathbf{k}}$such that ${\mathit{r}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{r}}_{\mathbf{i}\mathbf{2}\mathbf{.}\mathbf{i}\mathbf{3}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{r}}_{\mathbf{i}\left(k-1\right)\mathbf{,}\mathbf{i}\mathbf{k}\mathbf{,}}{\mathit{r}}_{\mathbf{i}\mathbf{k}\mathbf{+}\mathbf{1}}\mathbf{>}\mathbf{1}$. This means that by starting with a unit of currency ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$and then successively converting it to currencies ${\mathit{c}}_{\mathbf{i}\mathbf{1}\mathbf{,}}{\mathit{c}}_{\mathbf{i}\mathbf{2}}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}{\mathit{c}}_{\mathbf{i}\mathbf{k}}$, and finally back to ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$, you would end up with more than one unit of currency ${\mathit{c}}_{\mathbf{i}\mathbf{1}}$ . Such anomalies Last only a fraction of a minute on the currency exchange, but they provide an opportunity for risk-free profits.

b. Give an efficientalgorithm for detecting the presence of such an anomaly. Use the graph representation you found above.

Short answer

answer is not avaiable.

Step-by-step solution

Step-1: Shortest Path Problem

Dijkstra algorithm is an application of single source shortest path. Dijkstra’s algorithm also known as SPF algorithm and is an algorithm for finding the shortest paths between the vertices in a graph. It returns a search tree for all the paths the given node can take. An acyclic graph is a directed graph that has no cycles. Its operation is performed in the minheap.

The shortest path issue in graph theory is the task of finding a path between two vertex (or nodes) in a graph that minimizes the total of the weights of its constituent edges. For multiplicative weights, the generalised shortest path issue can be resolved quickly. The solution is to invert Dijkstra's algorithm.

Dijkstra’s algorithm is a single-source shortest path problem. It is used in both directed and undirected graph with non negative weight.

Step-2: Algorithm for finding best rate.

a).

• The currencies are represented as the vertex set of V of a full directed graph G, and the exchange rates are represented as the graph's edges E.
• Picking the ideal exchange rate from s to t is equivalent to having the path with the biggest exchange rate product.
• Then weight the edges with the negative logs of each exchange rate to make this into a shortest path issue.
• Apply Bellman-Ford to calculate the shortest path because edges can be negative.

It can be represented as:

1: function $bestcaseC\left(s,t\right)$

2: complete Directed Graph,

edge lengths

$⥍=\left\{-\log \overline{)\left(r_{i,j}\right)}\left(i.j\right)\in E\right\}$

3: $dist,prev\leftarrow bellmanford\left(G,I,S\right)$

Step-3: Algorithm for finding detecting the presence of anamaly.

b)

After$\left|V\right|$rounds, simply repeat the updating method. A negative cycle, i.e. a cycle is guaranteed to occur if any distance is updated.

1: function $Arbitrage\left(G_1\right)$

2:dist,prev$\leftarrow Bellmanford\left(G,I,s\right)$

3: $dis{t}^{*}\leftarrow$ all edges one more time

4: return True if for some $v,d$,

$ist\left[v\right]>dis{t}^{*}\left[v\right].dist\left[v\right]>dis{t}^{*}\left[v\right]$

Both issues can be answered using a modified Bellman-Ford algorithm that focuses on multiplication and maximisation rather than addition and minimization.