Data Structures & Algorithms – Dynamic programming (e.g. Bellman-Ford, Floyd-Warshall)

Dynamic Programming (DP) is a technique used to solve problems by breaking them down into smaller subproblems and solving each subproblem only once. The solutions to the subproblems are then stored in a table so that they can be reused for future subproblems, reducing the overall time complexity of the algorithm. DP is particularly useful for solving problems that have overlapping subproblems, such as optimization problems, where the goal is to find the best solution among a set of possibilities. Some examples of dynamic programming algorithms include:

1. Bellman-Ford algorithm: Bellman-Ford algorithm is a shortest path algorithm that can be used to find the shortest path from a single source node to all other nodes in a weighted graph, even if the graph contains negative edge weights. The algorithm works by iteratively relaxing the edges of the graph, where relaxing an edge means updating the shortest distance to a node if a shorter path is found. The time complexity of Bellman-Ford algorithm is O(VE), where V is the number of vertices and E is the number of edges.

Here is an example of the Bellman-Ford algorithm implemented in Python:

def bellman_ford(graph, source):
    distance = {vertex: float('infinity') for vertex in graph}
    distance[source] = 0

    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor in graph[vertex]:
                if distance[vertex] + graph[vertex][neighbor] < distance[neighbor]:
                    distance[neighbor] = distance[vertex] + graph[vertex][neighbor]

    for vertex in graph:
        for neighbor in graph[vertex]:
            if distance[vertex] + graph[vertex][neighbor] < distance[neighbor]:
                print("Negative weight cycle detected!")
                return

    return distance

graph = {
    'A': {'B': -1, 'C':  4},
    'B': {'C':  3, 'D':  2, 'E':  2},
    'C': {},
    'D': {'B':  1, 'C':  5},
    'E': {'D': -3}
}
print(bellman_ford(graph, 'A'))

2. Floyd-Warshall algorithm: Floyd-Warshall algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights and also for finding transitive closure of a relation R. It can also detect negative cycles. The algorithm works by iteratively updating the shortest distance between all pairs of vertices in the graph. The time complexity of Floyd-Warshall algorithm is O(V^3)

Here is an example of the Floyd-Warshall algorithm implemented in Python:

def floyd_warsh
all(graph):
distance = [[float('infinity') for _ in range(len(graph))] for _ in range(len(graph))]

for i in range(len(graph)):
    for j in range(len(graph)):
        if i == j:
            distance[i][j] = 0
        elif graph[i][j] != float('infinity'):
            distance[i][j] = graph[i][j]

for k in range(len(graph)):
    for i in range(len(graph)):
        for j in range(len(graph)):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])

for i in range(len(graph)):
    if distance[i][i] < 0:
        print("Negative weight cycle detected!")
        return

return distance

graph = [[0, 3, 8, float('infinity'), -4],
[float('infinity'), 0, float('infinity'), 1, 7],
[float('infinity'), 4, 0, float('infinity'), float('infinity')],
[2, float('infinity'), -5, 0, float('infinity')],
[float('infinity'), float('infinity'), float('infinity'), 6, 0]]
print(floyd_warshall(graph))

As you can see the two examples are implemented in Python, you can also implement these algorithms in Javascript, Java and Rust. In conclusion, dynamic programming is a technique used to solve problems by breaking them down into smaller subproblems and storing the solutions to these subproblems in a table to reduce the overall time complexity of the algorithm. Bellman-Ford algorithm and Floyd-Warshall algorithm are two examples of dynamic programming algorithms that can be used to find the shortest path in a weighted graph even if the graph contains negative edge weights and detect negative cycles. They can be implemented in various programming languages such as Python, JavaScript, Java and Rust.