最短路径(迪杰斯特拉算法)-ag真人游戏

例如，要求下图v0到v8的最短路径

所以我们可以找到这样的一条最短路径

下面是他的邻接矩阵：

伪代码如下：

#define maxvex	9
#define	infinity	65535
typedef	int	patharc[maxvex];			// 用于存储最短路径下标的数组
typedef int	shortpathtable[maxvex];		// 用于存储到各点最短路径的权值和
void shortestpath_dijkstar(mgraph g, int v0, patharc *p, shortpathtable *d)
{
	int v, w, k, min;
	int final[maxvex];		// final[w] = 1 表示已经求得顶点v0到vw的最短路径
	// 初始化数据
	for (v = 0; v < g.numvertexes; v  )
	{
		final[v] = 0;				// 全部顶点初始化为未找到最短路径
		(*d)[v] = g.arc[v0][v];		// 将与v0点有连线的顶点加上权值
		(*p)[v] = 0;				// 初始化路径数组p为0
	}
	(*d)[v0] = 0;		// v0至v0的路径为0
	final[v0] = 1;		// v0至v0不需要求路径
	// 开始主循环，每次求得v0到某个v顶点的最短路径
	for (v = 1; v < g.numvertexes; v  )
	{
		min = infinity;
		for (w = 0; w < g.numvertexes; w  )
		{
			if (!final[w] && (*d)[w] < min)
			{
				k = w;
				min = (*d)[w];
			}
		}
		final[k] = 1;	// 将目前找到的最近的顶点置1
		// 修正当前最短路径及距离
		for (w = 0; w < g.numvextexes; w  )
		{
			// 如果经过v顶点的路径比现在这条路径的长度短的话，更新！
			if (!final[w] && (min   g.arc[k][w] < (*d)[w]))
			{
				(*d)[w] = min   g.arc[k][w];	// 修改当前路径长度
				(*p)[w] = k;					// 存放前驱顶点
			}
		}
	}
}

最后的：