floyd warshall Algorithm

The Floyd-Warshall algorithm is a dynamic programming approach to find the shortest path between all pairs of nodes in a weighted graph with positive or negative edge weights, but without negative cycles. Developed by Robert Floyd and Stephen Warshall, it is an efficient method for solving the all-pairs shortest path problem, which is crucial in various applications such as network routing, travel planning, and social network analysis. The algorithm has a time complexity of O(n^3), where n is the number of vertices in the graph, making it a suitable choice for small to moderately-sized graphs. The core idea behind the Floyd-Warshall algorithm is to iteratively update the distance between each pair of nodes by considering an intermediate node that potentially reduces the path length between them. Initially, the distance matrix is populated with the direct edge weights between nodes or with infinity if there is no direct edge. Then, for each intermediate node, the algorithm checks if the distance between a pair of nodes can be reduced by going through the intermediate node. If so, the distance matrix is updated with the shorter path. After considering all intermediate nodes, the final distance matrix contains the shortest path between all pairs of nodes, which can be easily retrieved for any desired pair. 
import math
 
 
class Graph:
    def __init__(self, N=0):  # a graph with Node 0,1,...,N-1
        self.N = N
        self.W = [
            [math.inf for j in range(0, N)] for i in range(0, N)
        ]  # adjacency matrix for weight
        self.dp = [
            [math.inf for j in range(0, N)] for i in range(0, N)
        ]  # dp[i][j] stores minimum distance from i to j
 
    def addEdge(self, u, v, w):
        self.dp[u][v] = w
 
    def floyd_warshall(self):
        for k in range(0, self.N):
            for i in range(0, self.N):
                for j in range(0, self.N):
                    self.dp[i][j] = min(self.dp[i][j], self.dp[i][k] + self.dp[k][j])
 
    def showMin(self, u, v):
        return self.dp[u][v]
 
 
if __name__ == "__main__":
    graph = Graph(5)
    graph.addEdge(0, 2, 9)
    graph.addEdge(0, 4, 10)
    graph.addEdge(1, 3, 5)
    graph.addEdge(2, 3, 7)
    graph.addEdge(3, 0, 10)
    graph.addEdge(3, 1, 2)
    graph.addEdge(3, 2, 1)
    graph.addEdge(3, 4, 6)
    graph.addEdge(4, 1, 3)
    graph.addEdge(4, 2, 4)
    graph.addEdge(4, 3, 9)
    graph.floyd_warshall()
    graph.showMin(1, 4)
    graph.showMin(0, 3)

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go