ALL PAIRS SHORTEST PATH USING DYNAMIC PROGRAMMING

DESCRIPTION

• The All Pairs Shortest Path is also known as Floyd-Warshall ALgorithm, this algorithm is used to find all shortest distances between every pair of vertices in a Directed Graph with weights.
• As a result of this algorithm, it will generate a matrix, which will represent the minimum distance from any node to all other nodes in the graph.
• At first, the output matrix is the same as the given cost matrix of the graph. After that, the output matrix will be updated with all vertices k as the intermediate vertex.
• We initialize the solution matrix same as the input graph matrix as a first step. 
• Then we update the solution matrix by considering all vertices as intermediate vertex. 
• The idea is to one by one pick all vertices and updates all shortest paths which include the picked vertex as an intermediate vertex in the shortest path.

EXPLANATION

• Let G=(V, E) be a directed graph with n vertices.
• Let cost be a cost adjacency matrix for G such that

1. cost(i, i) = 0                       if 1 <= i <= n
2. cost(i, j) = cost(i, j)            if (i, j) is part of G
3. cost(i, j) = Infinite              if i is not equal to j and (i , j) is not part of G

• The all-paths shortest-problem is to determine a matrix A such that A(i, j) is the length of the shortest path from i to j.
• Ak(, j) = min{Ak-1(i, j) , Ak-1(i, k) + Ak-1(k, j)} ,   k >= 1

ALGORITHM

GRAPH

CODE

def floyd_warshall(n_v,graph):
  A = graph
  for k in range(n_v):
    for i in range(n_v):
      for j in range(n_v):
        A[i][j]= min( A[i][j], A[i][k]+ A[k][j] )

  print("\nThe Graph with All Shortest Paths ....\n")
  print(A)

n_v = int(input("Enter number of Vertices :"))
n_e = int(input("Enter number of Edges :"))
# let 99999 be infinte
graph = [[99999 for i in range(n_v)] for j in range(n_v)]

for i in range(n_v):
  for j in range(n_v):
    if(i==j):
      graph[i][j] = 0
      break
for i in range(n_e):
  x = int(input(f"Enter Source of Edge {i+1} :"))
  y = int(input(f"Enter Destination of Edge {i+1}:"))
  weight = int(input(f"Enter weight of Edge {i+1}:"))
  graph[x-1][y-1] =  weight

print("\nThe Entered Graph is ....")
print("Here 99999 is Infinte ....\n")
print(graph)
floyd_warshall(n_v,graph)

OUTPUT