Floyd_Warshal

Floyd_Warshal

 

#include<stdio.h>

#define IFNIT 9999999
typedef struct{
	int n;
	int L[500][500];
}Graph;
void init_graph(Graph *G, int n){
	G->n=n;
	int i,j;
	for(i=1;i<=G->n;i++)
		for(j=1;j<=G->n;j++)
			G->L[i][j]=0;
}
void add_graph(Graph *G, int x, int y, int w){
	G->L[x][y]=w;
}
int pi[100][100];
int next[100][100];
void Floyd_Warshall(Graph *G){
	int i,j,k;
	for(i=1;i<=G->n;i++){
		for(j=1;j<=G->n;j++){
			pi[i][j]=IFNIT;
			next[i][j]=-1;
		}
	}
	for(i=1;i<=G->n;i++){
		pi[i][i]=0;
	}
	for(i=1;i<=G->n;i++)
		for(j=1;j<=G->n;j++)
			if(G->L[i][j]!=0){
				pi[i][j]=G->L[i][j];
				next[i][j]=j;
			}
	for(k=1;k<=G->n;k++)
		for(i=1;i<=G->n;i++)
			for(j=1;j<=G->n;j++){
				if(pi[i][k]+pi[k][j] < pi[i][j]){
					pi[i][j]=pi[i][k]+pi[k][j];
					next[i][j]=next[i][k];
				}
			}
}

int main(){
	Graph G;
	int n,i,m,w,j;
	int u,v;
	freopen("dt.txt","r",stdin);
	scanf("%d%d",&n,&m);
	init_graph(&G,n);
	for(i=1;i<=m;i++){
			scanf("%d%d%d",&u,&v,&w);
			add_graph(&G,u,v,w);
	}
	Floyd_Warshall(&G);
	for(i=1;i<=G.n;i++){
		for(j=1;j<=G.n;j++){
			if(pi[i][j]>IFNIT-100000)
				printf("%d -> %d: oo\n",i,j);
			else
				printf("%d -> %d: %d\n",i,j,pi[i][j]);
		}
	}
	return 0;		
}