All Pairs Shortest Path

Find the all pairs shortest path by using Floud Warshall algorithm

Usage

floyd_warshall(graph: Graph, type: int)

Parameters:
      graph : Graph
            Graph Object
      type : int
            Type of floyd variant to perform
            Shortest Path (Type = 1)
            Reachability (Type = 2)
            Cycle Detection (Type = 3)

Returns:
      tuple
            A tuple of 2 elements. The first element is the matrix of the result. The second element is the mapping of the vertice number to 0 based indexing.

Example

from jellybeans.algos import floyd_warshallfrom jellybeans.structures import Graphg = Graph()g.add_vertex(0)g.add_vertex(1)g.add_vertex(2)g.add_vertex(3)g.add_vertex(4)g.add_edge(0, 1, 2)g.add_edge(0, 2, 1)g.add_edge(0, 4, 3)g.add_edge(1, 3, 4)g.add_edge(2, 1, 1)g.add_edge(2, 4, 1)g.add_edge(3, 0, 1)g.add_edge(3, 2, 3)g.add_edge(3, 4, 5)res, _ = floyd_warshall(g, 1)print(res) # [[0, 2, 1, 6, 2], [5, 0, 6, 4, 7], [6, 1, 0, 5, 1], [1, 3, 2, 0, 3], [1000000000, 1000000000, 1000000000, 1000000000, 0]]res, _ = floyd_warshall(g, 2)print(res) # [[1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0]] # 1 denotes reachable and 0 denotes not reachableres, _ = floyd_warshall(g, 3)print(res) # [[7, 2, 1, 6, 2], [5, 7, 6, 4, 7], [6, 1, 7, 5, 1], [1, 3, 2, 7, 3], [1000000000, 1000000000, 1000000000, 1000000000, 1000000000]] # if [i][j] != 1000000000 when i == j, a cycle is present.