最短路径(多源floyd_warshall邻接阵形式)代码,C/C++代码库,德仔网

代码语言

代码分类

【C/C++】最短路径(多源floyd_warshall邻接阵形式)

作者:旭融 / 发布于2016/3/15/ 548

//多源最短路径,floyd_warshall算法,复杂度O(n^3)
//求出所有点对之间的最短路经,传入图的大小和邻接阵
//返回各点间最短距离min[]和路径pre[],pre[i][j]记录i到j最短路径上j的父结点
//可更改路权类型,路权必须非负!
#define MAXN 200
#define inf 1000000000
typedef int elem_t;

void floyd_warshall(int n,elem_t mat[][MAXN],elem_t min[][MAXN],int pre[][MAXN]){
	int i,j,k;
	for (i=0;i<n;i++)
		for (j=0;j<n;j++)
			min[i][j]=mat[i][j],pre[i][j]=(i==j)?-1:i;
	for (k=0;k<n;k++)
		for (i=0;i<n;i++)
			for (j=0;j<n;j++)
				if (min[i][k]+min[k][j]<min[i][j])
					min[i][j]=min[i][k]+min[k][j],pre[i][j]=pre[k][j];
}

试试其它关键字

同语言下

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

可能有用的

.C分鱼问题
.链表
.最大连续和
.编码字符串
.libiconv字符编码处理及判断字符串是否为utf8
.一组数中两两二元组，差最大有几对，差最小呢？（数组
.通过管道获取一个进程的执行状态
.多关键字排序
.字符串字典序排序
.3元一次方程(牛顿迭代法求方程的根)

旭融贡献的其它代码(8)

.Map遍历的几种方法
.执行一个命令,在等待15秒后,没有这个命令的结果,就执
.checkbox进行全选操作
.关闭窗口代码段
.最短路径(多源floyd_warshall邻接阵形式)
.执行cmd命令，并返回字符串
.查询日志查看数据库历史查询记录的方法
.asp.net 实现桌面快捷方式