Single-Source Shortest Path Problem

Shortest Path Problem

The shortest path problem in graph theory is the task of determining the path between any two vertices (or nodes) in a graph such that the sum of the weights along each of its constituent edges is as small as possible.

Most people think of Dijkstra's algorithm—also known as "Dijkstra's Shortest Path First algorithm"—when attempting to determine the shortest path in a graph. Dijkstra's algorithm is unquestionably useful; however, it cannot handle negative edge weights.

In order to deal with negative edge weights, let's discuss the "Bellman-Ford algorithm."

Bellman-Ford Algorithm

The Bellman–Ford algorithm is an algorithm that computes the shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers.

The algorithm was first proposed by Alfonso Shimbel in 1955 but is instead named after Richard Bellman and Lester Ford Jr., who published it in 1958 and 1956, respectively.?Edward F. Moore also published a variation of the algorithm in 1959, and for this reason, it is also sometimes called the Bellman–Ford–Moore algorithm.

What is Bellman-Ford Algorithm

The Bellman–Ford algorithm works on the "Principle Of Relaxation."

The algorithm initially overestimates the distance along the path from the starting vertex to all other vertices. It then gradually reduces (relaxes) those estimations by identifying new paths that are shorter than the inflated ones.

If there is no negative cycle, executing this repeatedly for all vertices assures that the resulting shortest path is optimized.

How does Bellman-Ford Algorithm work?

1. Initialize distances from the source to all vertices as infinite and distance to the source itself as 0. I.e., Create an array distance[] of size |V| with all values as infinite except distance[source], where the source is the source vertex.
2. Calculate the shortest distances.

3. This step identifies if there is a negative weight cycle in the graph.

The idea of step 3 is that step 2 guarantees the shortest distances if the graph doesn’t contain a negative weight cycle. If we iterate through all edges one more time and get a shorter path for any vertex, then there is a negative weight cycle.

Pseudocode

Function bellmanFordAlgorithm(G) # G is the graph

  dist[V] = ?infinite # dist is distance?
  
??dist[src] = 0 # src is source

  n = |V| # no of edges

  for (n – 1) times:
    relax(G, dist)
      
  # relax one more time to detect negative edge
  relax(G, dist)
  
# --- End Function  ?
  
Function relax(G, dist) # G is graph and dist is distance

??for each vertex V in G
????for each edge (u,v) in G
??????if ?dist[u] + edgeweight(u, v) < dist[v]:
        update dist[v]h        

Use case of ?Bellman-Ford Algorithm

Currency Arbitrage

Currency arbitrage is a forex trading method in which a trader purchases and sells currencies in several markets in an effort to profit from price differences.

With no open currency exposure, forex trading is a risk-free trading method that generates profits for traders. To take advantage of any pricing inefficiencies, this kind of arbitrage trading entails buying and selling various currency pairings.?

How can we detect Arbitrage?

Let's assume that we are familiar with three different currencies, such as USD, CAD, and GBP, as well as their exchange rates. With this knowledge, we can decide whether or not there is room for arbitrage, that is if there is a certain set of deals we can execute starting with some amount X of any currency and ending with some amount more than amount X of the same currency.

Let's pretend for the purpose of simplicity that there are no transaction fees and that you can exchange any quantity of money in fractional amounts.

How can this be solved?

Let’s represent the currency as a 2D Matrix

In the matrix above, we can see that row “0” represents USD, which means that row “0” contains the exchange rates for “1” USD to all other currencies.

Since row “1” represents CAD, index “1” in the USD row contains the exchange for USD to CAD.

Code

# Basics: https://www.youtube.com/watch?v=75yC1vbS8S8&ab_channel=takeUforwar


# Tc: O(n^3) | O(n^2)
# Bellman Ford Algorithm - Single Source Shortest Path

import math
def detectArbitrage(exchangeRates):
? ? # convert all the edges to negative log: either log10, log2 or loge
? ? logExchangeRates = convertToLog(exchangeRates)
? ? print(logExchangeRates)


? ? # bellman Ford algorithm - if we can find a cycle of vertices such that the sum of their weights if negative, then we can conclude there exists an opportunity for currency arbitrage.?
? ? return bellmanFord(logExchangeRates)


def convertToLog(matrix):
? ? row_len = len(matrix)
? ? col_len = len(matrix[0])


? ? logMatrix = [[None for _ in range(col_len)] for _ in range(row_len)]


? ? for i in range(row_len):
? ? ? ? for j in range(col_len):
? ? ? ? ? ? # convert each value to negative log
? ? ? ? ? ? negative_log = -math.log2(matrix[i][j])
? ? ? ? ? ? logMatrix[i][j] =? negative_log
? ??
? ? return logMatrix




def bellmanFord(graph):
? ? n = len(graph)


? ? # create a distance array
? ? distance = [math.inf] * n
? ? distance[0] = 0


? ? # relax the edges for n - 1 time
? ? for _ in range(n-1):


? ? ? ? # so if the value stops decresing in at some point return False
? ? ? ? if not relaxEdges(distance, graph):
? ? ? ? ? ? return False


? ? # at this point we found the shortest path and no further changes can be made
? ? # but if our value changes - then we have negative cycle
? ? return relaxEdges(distance, graph)


def relaxEdges(distance, graph):
? ? # u = node, v = child
? ? # dist[v] = dist[u] + weight of edge < dist[v]

? ? update = False # check if the value is changing


? ? for sourceIdx, edges in enumerate(graph):
? ? ? ? for destinationIdx, weight in enumerate(edges):
? ? ? ? ? ? # u = node, v = child -- dist[u] + weight of edge < dist[v]
? ? ? ? ? ? if distance[sourceIdx] + weight < distance[destinationIdx]:
? ? ? ? ? ? ? ? update = True # the value
? ? ? ? ? ? ? ? distance[destinationIdx] = distance[sourceIdx] + weight
? ??
? ?
? ? return update
? ??        

Arbitrage opportunities arise when a cycle is determined. The matrix is initially transformed into a negatively weighted graph. Next, we look for a cycle. Arbitrage is present if a cycle is found. Fortunately, with the Bellman-Ford algorithm, we can detect negative weight cycles in O(|V*E|) time.

Conclusion

The Bellman-Ford algorithm is an important algorithm for solving single-source shortest-path problems in a graph where some of the edge weights may be negative.

The algorithm is able to handle graphs with negative edge weights by using a dynamic programming approach and relaxing the edges in a specific order.

One of the main advantages of the Bellman-Ford algorithm is that it can detect negative weight cycles in a graph.

If the algorithm is run on a graph with a negative weight cycle, it will detect this cycle and report that the shortest path problem has no solution. This is particularly useful in scenarios where the edge weights are not known in advance and may change over time.

Another important feature of the Bellman-Ford algorithm is that it can handle graphs that are not strongly connected, unlike Dijkstra's algorithm, which requires a non-negative edge weight and only works with strongly connected graphs.

The Bellman-Ford algorithm is used in a wide range of applications, including:

• Network routing protocols, such as the Routing Information Protocol (RIP) and the Open Shortest Path First (OSPF) protocol, use variations of the Bellman-Ford algorithm to determine the best routes for data packets to take through a network.
• In transportation and logistics, the Bellman-Ford algorithm can be used to plan routes that take into account factors such as traffic and road conditions and to find alternative routes in case of disruptions or delays.
• In financial modeling, the Bellman-Ford algorithm can be used to evaluate investment strategies and to model portfolio risk.

Overall, the Bellman-Ford algorithm is an important algorithm for solving single-source shortest path problems in graphs with negative edge weights, it can detect negative weight cycles and handle graphs that are not strongly connected, making it a powerful and versatile algorithm.

GitHub

References:

https://www.youtube.com/watch?v=75yC1vbS8S8&ab_channel=takeUforward

Images: Google Search, Simplilearn, GeeksForGeeks, Mathematica & Wolfram Language.