算法导论-25.2-Floyd-Wasrshall算法

一、介绍

二、代码

#include <iostream>
#include <algorithm>
using namespace std;

#define N 6//点的个数
#define M 10//边的个数
//邻接矩阵
struct Graph
{
	int map[N+1][N+1];
	int row;
	Graph(int n):row(n)
	{
		int i, j;
		for(i = 1; i <= N; i++)
		{
			for(j = 1; j <= N; j++)
				if(i == j)
					map[i][j] = 0;
				else
					map[i][j] = 0x7fffffff;
		}
	}
	Graph(Graph &G)
	{
		row = G.row;
		int i, j;
		for(i = 1; i <= N; i++)
		{
			for(j = 1; j <= N; j++)
				map[i][j] = G.map[i][j];
		}
	}
};
int min(int a, int b)
{
	return a < b ? a : b;
}
void Print(Graph G)
{
	int i, j;
	for(i = 1; i <= N; i++)
	{
		for(j = 1; j <= N; j++)
			cout<<G.map[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
void Floyd_Warshall(Graph W)
{
	int n = W.row;
	Graph D(W);
	int i, j, k;
	for(k = 1; k <= n; k++)
	{
		for(i = 1; i <= n; i++)
		{
			for(j = 1; j <= n; j++)
			{
				if(D.map[i][k]!=0x7fffffff && D.map[k][j]!=0x7fffffff)
					D.map[i][j] = min(D.map[i][j], D.map[i][k]+D.map[k][j]);
			}
		}
		Print(D);
	}
}
Graph Transitive_Closure(Graph G)
{
	int n = G.row, i, j, k;
	Graph T(n);
	for(i = 1; i <= n; i++)
	{
		for(j = 1; j <= n; j++)
		{
			if(i == j || G.map[i][j] != 0x7fffffff)
				T.map[i][j] = 1;
			else
				T.map[i][j] = 0;
		}
	}
	for(k = 1; k <= n; k++)
	{
		for(i = 1; i <= n; i++)
		{
			for(j = 1; j <= n; j++)
				T.map[i][j] = min(T.map[i][j], T.map[i][k]+T.map[k][j]);
		}
	}
	return T;
}



/*
1 5 -1
2 1 1
2 4 2
3 2 2
3 6 -8
4 1 -4
4 5 3
5 2 7
6 2 5
6 3 10
*/
/*
1 3 2
1 5 -4
1 3 8
2 5 7
2 4 1
3 2 4
4 1 2
4 3 -5
5 4 6
*/
int main()
{
	int i, start, end, value;
	Graph G(N);
	for(i = 1;i <= M; i++)
	{
		cin>>start>>end>>value;
		G.map[start][end] = value;
	}
	Print(G);
	Floyd_Warshall(G);
	return 0;
}#include <iostream>
#include <alg