floyd warshall algorithm python code example

Example 1: floyd warshall algorithm python

# Number of vertices
nV = 4
INF = 999

# Algorithm 
def floyd(G):
    dist = list(map(lambda p: list(map(lambda q: q, p)), G))

    # Adding vertices individually
    for r in range(nV):
        for p in range(nV):
            for q in range(nV):
                dist[p][q] = min(dist[p][q], dist[p][r] + dist[r][q])
    sol(dist)

# Printing the output
def sol(dist):
    for p in range(nV):
        for q in range(nV):
            if(dist[p][q] == INF):
                print("INF", end=" ")
            else:
                print(dist[p][q], end="  ")
        print(" ")

G = [[0, 5, INF, INF],
         [50, 0, 15, 5],
         [30, INF, 0, 15],
         [15, INF, 5, 0]]
floyd(G)

Example 2: floyd warshall algorithm c program

#include<stdio.h>#include<conio.h>int min(int,int);void floyds(int p[10][10],int n) {	int i,j,k;	for (k=1;k<=n;k++)	  for (i=1;i<=n;i++)	   for (j=1;j<=n;j++)	    if(i==j)	     p[i][j]=0; else	     p[i][j]=min(p[i][j],p[i][k]+p[k][j]);}int min(int a,int b) {	if(a<b)	  return(a); else	  return(b);}void main() {	int p[10][10],w,n,e,u,v,i,j;	;	clrscr();	printf("\n Enter the number of vertices:");	scanf("%d",&n);	printf("\n Enter the number of edges:\n");	scanf("%d",&e);	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   p[i][j]=999;	}	for (i=1;i<=e;i++) {		printf("\n Enter the end vertices of edge%d with its weight \n",i);		scanf("%d%d%d",&u,&v,&w);		p[u][v]=w;	}	printf("\n Matrix of input data:\n");	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   printf("%d \t",p[i][j]);		printf("\n");	}	floyds(p,n);	printf("\n Transitive closure:\n");	for (i=1;i<=n;i++) {		for (j=1;j<=n;j++)		   printf("%d \t",p[i][j]);		printf("\n");	}	printf("\n The shortest paths are:\n");	for (i=1;i<=n;i++)	  for (j=1;j<=n;j++) {		if(i!=j)		    printf("\n <%d,%d>=%d",i,j,p[i][j]);	}	getch();}