弗洛伊德(Floyed)算法

作者：追风剑情发布于：2014-10-6 17:12 分类：Algorithms

求每对顶点之间的最短路径

开发工具 Visual Studio2010

开发语言 C++

#include <stdlib.h>
#include <stdio.h>

const int MAXVEX = 6;//最大顶点数
const int INF = 429496729;//无路径时的权值

/**
 * 求每对顶点之间的最短路径
 * 弗洛伊德(Floyed)算法
 */
void Floyed(int cost[][MAXVEX], int n)
{
	int A[MAXVEX][MAXVEX], path[MAXVEX][MAXVEX];
	int i,j,k,pre;
	for(i=0; i<n; i++)
		for(j=0; j<n; j++)
		{
			A[i][j] = cost[i][j];
			path[i][j] = -1;
		}

	for(k=0; k<n; k++)
	{
		for(i=0; i<n; i++)
		{
			for(j=0; j<n; j++)
			{
				if(A[i][j] > A[i][k] + A[k][j])
				{
					A[i][j] = A[i][k] + A[k][j];
					path[i][j] = k;
				}
			}
		}
	}

	printf("\n Floyed 算法求解如下：
");
	for(i=0; i<n; i++) //输出最短路径
	{
		for(j=0; j<n; j++)
		{
			if(i != j){
				printf("%d->%d:", i, j);
				if(A[i][j] == INF){
					printf("不存在路径
");
				}else{
					printf("路径长度为：%3d ", A[i][j]);
					printf("路径为%d ", i);
					pre = path[i][j];
					while(pre != -1){
						printf("%d ", pre);
						pre = path[pre][j];
					}
					printf("%d\n", j);
				}
			}
		}
	}
}

void main()
{
	//定义一个代价矩阵作为测试数据 INF:无路径
	int cost[6][MAXVEX] = {
		{0,   50,  10,  INF, INF, INF},
		{INF, 0,   15,  50,  10,  INF},
		{20,  INF, 0,   15,  INF, INF},
		{INF, 20,  INF, 0,   35,  INF},
		{INF, INF, INF, 30,  0,   INF},
		{INF, INF, INF, 3,   INF, 0  }
	};
 
	Floyed(cost, 6);

	printf("\n");
	system("pause");
}