图算法——求最短路径（Floyd算法）

求图的最短路径在实际生活中有许多应用，比如说在你在一个景区的某个景点，参观完后，要怎么走最少的路程到你想参观的下个景点，这就利用到了求图最短路径的算法。求图的最短路径有很多算法，这里介绍一种弗洛伊德（Floyd）算法来求图的最短路径。

在介绍算法前，需要掌握一点图的基本知识，比如说什么是路径，什么是路径长度等。如果对这些不了解的话，建议先了解一下。

这是我写的一篇博客，对图的一些基本知识的简介——图的一些基本知识。

一、什么是最短路径

在网图和非网图中，最短路径的含义是不同的。由于非网图没有边上的权值，所谓最短路径，其实指的就是两个顶点之间经过的边数最少的路劲（即可以理解为把每一条边的权值看作是1）。

对于网图来说，所谓最短路径，就是指两顶点之间经过的边上的权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点。

求带权有向图G的最短路径问题一般可分为两类：一是单源最短路径，即求图中某一个顶点到其它顶点的最短路径，可以通过经典的 Dijkstra（迪杰斯特拉）算法求解（这是我写的一篇博客，有兴趣的同学可以看下，Dijkstra算法）；二是求每对顶点间的最短路径，可通过Floyd（弗洛伊德）算法（也是我接下来要讲解的算法）来求解。

二、弗洛伊德（Floyd）算法

Floyd算法需要两个二维数组 D[vexNum][vexNum] 和 P[vexNum][vexNum]，其中 vexNum代表的是图中结点的个数，D代表顶点到顶点的最短路径权值和的矩阵。P代表对应顶点的最短路径的前驱矩阵，用来存储路径。

Floyd算法的基本思路是：递推产生一个 n 阶方阵序列 $D^{(-1)}$ ， $D^{(0)}$ ，… ， $D^{(k)}$ ，…， $D^{(n-1)}$ 和 $P^{(-1)}$ ， $P^{(0)}$ ，…， $P ^{(k)}$ ，…， $P^{(n-1)}$ 。其中 $D^{(k)}$

初始时，对于任意两个顶点 v 和 w，若它们之间存在边，则以此边上的权值作为它们之间的最短路径长度；若它们之间不存在有向边，则以 ∞ 作为它们之间的最短路径，此过程用于初始化矩阵D。以后逐步在原路径中加入顶点 k（k=0,1,…,n-1）作为中间顶点。若增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路劲并且修改矩阵 P。算法描述如下：

定义一个 n 阶方阵序列 $D^{(-1)}$ ， $D^{(0)}$ ，…， $D^{(n-1)}$ ,其中，

$D^{(k)}$ [v][w] = Min{ $D^{(k-1)}$ [v][w]， $D^{(k-1)}$ [v][k] + $D^{(k-1)}$ [k][w]}

$P^{(k)}$ [v][w] = $P^{(k)}$ [v][k]

上式中， $D^{(0)}$ [v][w]是从顶点 v 到 w、中间顶点是 $V_{0}$ 的最短路径长度， $D^{(k)}$ [v][w]是从顶点 v 到 w，中间顶点的序号不大于 k 的最短路径长度。Floyd算法是一个迭代的过程，每迭代一次，在从 v

到 w 的最短路径上就多考虑了一个顶点；经过 n 次迭代后，所得到的 $D^{(n-1)}$ [v][w]就是 v 到 w 的最短路径长度，即方阵 $D^{(n-1)}$ 中就保存了任意一对顶点之间的最短路径长度。方阵 $P^{(n-1)}$ 可以求出顶点 v 到顶点 w 的最短路径。

可能这么说，很多人可能是云里雾里的（其实我感觉我也表达不出那个意思，但通过下面这个实例我相信你们会理解这个算法的执行过程），上面的说法主要还是表明两个结点之间的距离可能并不是直线最短，可能两个结点通过中间结点会比两个结点之间原本直线的距离还短，然后按照这个思路得出最短路径。下面我将用一个实例，来模拟Floyd算法每一步的执行流程。在此之前先看下Floyd算法的代码实现：

/* Floyd算法 */
void ShortestPath_Floyd(MGraph G, Patharc P, ShortPathTable D)
{
	int v, w, k;
	for (v = 0; v < G.vexNum; v++)					// 初始化 D与P
	{
		for (w = 0; w < G.vexNum; w++)
		{
			D[v][w] = G.Edge[v][w];					// D[v][w]值即为对应点间的权值
			P[v][w] = w;
		}
	}
	/* Floyd算法的主要部分 */
	for (k = 0; k < G.vexNum; k++)
	{
		for (v = 0; v < G.vexNum; v++)
		{
			for (w = 0; w < G.vexNum; w++)
			{
				if (D[v][w] > (D[v][k] + D[k][w]))
				{	/* 如果经过下标为 k 顶点的路径比原来两点间路径更短 */
					D[v][w] = D[v][k] + D[k][w];	// 将当前两点间权值设更小一个
					P[v][w] = P[v][k];				// 路径设置为经过下标为 k 的顶点
				}
			}
		}
	}
	return;
}

实例：

算法执行流程：

初始化：

for (v = 0; v < G.vexNum; v++)					// 初始化 D与P
{
	for (w = 0; w < G.vexNum; w++)
	{
		D[v][w] = G.Edge[v][w];					// D[v][w]值即为对应点间的权值
		P[v][w] = w;
	}
}

第一轮：

将 $V_{0}$ 作为中间顶点，并对所有顶点对{v,w]，如果有 $D^{(-1)}$ [v][w] > $D^{(-1)}$ [v][0] + $D^{(-1)}$ [0][w]，则将 $D^{(-1)}$ [v][w] 更新为 $D^{(-1)}$ [v][0] + $D^{(-1)}$ [0][w]，发现无符合情况，不用更新，得到矩阵 $D^{(0 )}$ 和 $P^{(0)}$ 。

其计算过程是，列中的单个元素与中间顶点所对应的行的每个单个元素进行相加，并与其对应的列进行比较，如果小于，就进行更新D矩阵和P矩阵，否则不进行更新。如列中的单个元素 6，它与 V0 对应的行的每个元素相加后，再与对应的列比较，发现 6 + 0 = 6 == 6，6 + 6 = 12 > 0，6 + 3 = 9 > 2，然后依次类推发现没有符合的情况，故这V1一行不需要修改，接着往下也是如此进行下去。

第二轮：

将 $V_{1}$ 作为中间顶点，继续检测全部顶点对{v,w}，利用上述的计算方法，可以得出以上结果。

紧接着依次执行第三、第四、、、第六轮，得出以下结果：

至此算法结束。

三、测试程序

/*
使用此程序需输入以下内容创建图G：
第一步：7 12
第二步：0123456
第三步：依次输入下面的内容，输入完一行就按下换行键
0 1 6
0 2 3
1 2 2
1 3 1
1 4 4
2 3 5
2 5 7
3 4 3
3 5 6
4 5 2
4 6 2
5 6 3
*/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

#define MaxVerterNum 100		// 顶点数目的最大值
#define INFINITY 65535			// 用65535代表 ∞

typedef char VertexType;		// 顶点的数据类型
typedef int EdgeType;			// 带权图中边上权值的数据类型

/* 邻接矩阵的存储结构 */
typedef struct
{
	VertexType Vexs[MaxVerterNum];					// 顶点表
	EdgeType Edge[MaxVerterNum][MaxVerterNum];		// 邻接矩阵
	int vexNum, arcNum;								// 图当前顶点数和弧数
}MGraph;

/*清除缓冲区的换行符*/
void Clean(void)
{
	while (getchar() != '\n')
		continue;
}

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G);

/* 弗洛伊德（Floyd) 算法*/
typedef int Patharc[MaxVerterNum][MaxVerterNum];			// 用于存储最短路径下标的数组，从源点Vi到顶点Vj之间的最短路径的前驱
typedef int ShortPathTable[MaxVerterNum][MaxVerterNum];		// 用于存储到各点最短路径的权值和
void ShortestPath_Floyd(MGraph G, Patharc P, ShortPathTable D);

/* 输出最短路径 */
/* Floyd算法的结果输出 */
void Show_ShortestPath_Floyd(Patharc path, ShortPathTable dist, MGraph G);

/* 将Patharc矩阵和ShortPathTable矩阵输出出来 */
void Show_Matrix(int vexNum, Patharc P, ShortPathTable D);

int main(void)
{
	MGraph G;
	Patharc path;
	ShortPathTable dist;
	CreateMGraph(&G);
	ShortestPath_Floyd(G, path, dist);
	Show_ShortestPath_Floyd(path, dist, G);
	return 0;
}

/* 建立无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{
	int i, j, k, w;
	printf("请输入顶点数和边数：");
	scanf("%d %d", &G->vexNum, &G->arcNum);			// 获取无向图顶点数和边数
	printf("请输入全部顶点信息：\n");
	Clean();									    // 将换行符去除
	for (i = 0; i < G->vexNum; i++)					// 读取顶点信息，建立顶点表
		scanf("%c", &G->Vexs[i]);
	for (i = 0; i < G->vexNum; i++)
		for (j = 0; j < G->vexNum; j++)
			G->Edge[i][j] = INFINITY;				// 邻接矩阵初始化
	for (i = 0; i < G->vexNum; i++)
		G->Edge[i][i] = 0;
	for (k = 0; k < G->arcNum; k++)					// 读入arcNum条边，建立邻接矩阵
	{
		printf("请输入边（Vi, Vj)上的下标i，下标j和权w：\n");
		scanf("%d %d %d", &i, &j, &w);				// 获取边和权
		G->Edge[i][j] = w;							// 无向图矩阵对称
		G->Edge[j][i] = G->Edge[i][j];
	}
	return;
}

/* Floyd算法 */
void ShortestPath_Floyd(MGraph G, Patharc P, ShortPathTable D)
{
	int v, w, k;
	for (v = 0; v < G.vexNum; v++)					// 初始化 D与P
	{
		for (w = 0; w < G.vexNum; w++)
		{
			D[v][w] = G.Edge[v][w];					// D[v][w]值即为对应点间的权值
			P[v][w] = w;
		}
	}
	/* Floyd算法的主要部分 */
	for (k = 0; k < G.vexNum; k++)
	{
		for (v = 0; v < G.vexNum; v++)
		{
			for (w = 0; w < G.vexNum; w++)
			{
				if (D[v][w] > (D[v][k] + D[k][w]))
				{	/* 如果经过下标为 k 顶点的路径比原来两点间路径更短 */
					D[v][w] = D[v][k] + D[k][w];	// 将当前两点间权值设更小一个
					P[v][w] = P[v][k];				// 路径设置为经过下标为 k 的顶点
				}
			}
		}
		printf("中间结点为V%d时的 D 和 P 矩阵如下：\n", k);
		Show_Matrix(G.vexNum, P, D);
	}
	return;
}

/* 输出最短路径 */
/* Floyd算法的结果输出 */
void Show_ShortestPath_Floyd(Patharc path, ShortPathTable dist, MGraph G)
{
	int v, w, k;
	printf("各顶点间最短路径如下：\n");
	for (v = 0; v < G.vexNum; v++)
	{
		for (w = v + 1; w < G.vexNum; w++)
		{
			printf("V%d-V%d  weight:  %d ", v, w, dist[v][w]); // 打印顶点 v 到 顶点 w 的距离
			k = path[v][w];									 // 获得第一个路径顶点下标
			printf(" path: V%d", v);						// 打印源点
			while (k != w)									// 如果路径顶点下标不是终点，执行循环
			{
				printf(" -> V%d", k);						// 打印路径顶点
				k = path[k][w];								// 获得下一个路径顶点下标
			}
			printf(" -> V%d\n", w);							// 打印终点
		}
		printf("\n\n");
	}
	printf("\n");
}

/* 将Patharc矩阵和ShortPathTable矩阵输出出来 */
void Show_Matrix(int vexNum, Patharc P, ShortPathTable D)
{
	int i, j;
	printf("输出 D 矩阵：\n\n\n");
	for (i = 0; i < vexNum; i++) {
		for (j = 0; j < vexNum; j++)
			printf("%7d", D[i][j]);
		printf("\n");
	}
	printf("输出 P 矩阵：\n\n\n");
	for (i = 0; i < vexNum; i++) {
		for (j = 0; j < vexNum; j++)
			printf("%7d", P[i][j]);
		printf("\n");
	}
	return;
}

文章出处登录后可见！

已经登录？立即刷新

图算法——求最短路径（Floyd算法）

一、什么是最短路径

二、弗洛伊德（Floyd）算法

三、测试程序

相关推荐