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

代码语言

代码分类

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

作者:Hobart / 发布于2016/3/15/ 382

//单源最短路径,dijkstra算法,邻接阵形式,复杂度O(n^2)
//求出源s到所有点的最短路经,传入图的顶点数n,(有向)邻接矩阵mat
//返回到各点最短距离min[]和路径pre[],pre[i]记录s到i路径上i的父结点,pre[s]=-1
//可更改路权类型,但必须非负!
#define MAXN 200
#define inf 1000000000
typedef int elem_t;

void dijkstra(int n,elem_t mat[][MAXN],int s,elem_t* min,int* pre){
	int v[MAXN],i,j,k;
	for (i=0;i<n;i++)
		min[i]=inf,v[i]=0,pre[i]=-1;
	for (min[s]=0,j=0;j<n;j++){
		for (k=-1,i=0;i<n;i++)
			if (!v[i]&&(k==-1||min[i]<min[k]))
				k=i;
		for (v[k]=1,i=0;i<n;i++)
			if (!v[i]&&min[k]+mat[k][i]<min[i])
				min[i]=min[k]+mat[pre[i]=k][i];
	}
}

试试其它关键字

　最短路径　

同语言下

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

可能有用的

.C#实现的html内容截取
.List 切割成几份工具类
.SQL查询多列合并成一行用逗号隔开
.一行一行读取txt的内容
.C#动态修改文件夹名称(FSO实现，不移动文件)
.c# 移动文件或文件夹
.c#图片添加水印
.Java PDF转换成图片并输出给前台展示
.网站后台修改图片尺寸代码
.处理大图片在缩略图时的展示

Hobart贡献的其它代码(3)

.供应商 VENDOR
.最短路径(单源dijkstra邻接阵形式)
.Oracle&C# 导出多Sheet Excel ,使用Oracle Package