数据结构与算法（7-4）最短路径（迪杰斯特拉(Dijkstra)算法、弗洛伊德(Floyd)算法）
目录
一、最短路径概念
最短路径，顾名思义，两结点之间最短的路径（可以是非邻接结点）。
最小生成树和最短路径区别：
最小生成树：连通图的最短路径。
最短路径：两任意结点之间（可以非邻接）的最短路径。
二、迪杰斯特拉(Dijkstra)算法（单源最短路径）
优点：效率较高，时间复杂度为O(n^2)。
缺点：只能求一个顶点到所有顶点的最短路径。 （单源最短路）
1、原理
1、先选定一个根结点，并选定一个数组，先确定未遍历前的初始距离，把距离最短的邻接结点选定为中间结点，并标记访问过，开始往下遍历，挨个访问那个中间结点的邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离，作为新距离，对比新距离和旧距离，如果新距离大，则把新距离替换掉旧距离，否则不变。
2、一轮访问结束后，从未标记的结点中选定距离最短的，把它作为中间结点，继续往下访问。若都标记过，则算法结束。
2、过程
1、保存根结点及到其他结点的权（距离）
2、 访问最近结点作为中间结点
3、对比新距离（根结点到中间结点+中间结点到新结点）和旧距离（根结点直接到新结点）
4、若新距离短，修改保存到数组
5、继续访问后面的，把未访问的距离根最近结点作为中间结点，继续访问它的邻接结点
6、继续对比新距离和旧距离
7、若新距离短，则修改保存到数组
8、 继续以距离根结点最短的结点为对象，访问它的邻接结点
9、全部访问完毕，结束算法
欣赏一下自己的稿书： 
3、代码
//迪杰斯特拉(Dijkstra)算法
/*测试案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXSIZE 20
#define MAX 65535 //代表无穷大
int length = 0; //顶点个数
int root = 0; //根顶点
int rootDist[MAXSIZE]; //根顶点（记录根到其他顶点的距离）
bool visit[MAXSIZE]; //记录各结点是否访问
//图（顶点和权）
typedef struct
{
char vertex[MAXSIZE];
int weight[MAXSIZE][MAXSIZE]; //权可以代替边（自身为0，相连有值，不相连无穷大）
}Graph;
Graph G;
//输入顶点
void InputVertex()
{
int i;
char ch;
printf("请输入图的顶点：\n");
scanf("%c", &ch);
for (i = 0; i < MAXSIZE && ch != '\n'; i++)
{
G.vertex[i] = ch;
scanf("%c", &ch);
}
length = i;
}
//图权重初始化
void GraphWeightInit()
{
int i, j;
for (i = 0; i < length; i++)
{
for (j = 0; j < length; j++)
{
if (i == j) //指向自己
G.weight[i][j] = 0;
else
G.weight[i][j] = MAX; //无穷大
}
}
}
//根据数据查找图顶点下标
int FindIndex(char ch)
{
int i;
for (i = 0; i < length; i++)
{
if (G.vertex[i] == ch)
return i;
}
return -1;
}
//创建图
void CreateGraph()
{
int i, j, index, weight;
char ch;
for (i = 0; i < length; i++)
{
printf("请输入%c的邻接顶点及权重（空格分隔，换行结束）：\n", G.vertex[i]);
scanf("%c", &ch);
while (ch != '\n')
{
while (ch == ' ') //为空格
{
scanf("%c", &ch); //输入字符
continue;
}
index = FindIndex(ch);
scanf("%d", &weight); //输入权重
while (weight == 32) //32为空格的ASCII码
{
scanf("%d", &weight);
continue;
}
G.weight[i][index] = weight; //存入权重
scanf("%c", &ch); //(下一轮)输入字符
}
}
}
//根结点初始化
void Init()
{
int i;
printf("请输入根结点：\t");
scanf("%d", &root);
for (i = 0; i < length; i++)
{
rootDist[i] = G.weight[root][i]; //把0作为根，初始化
visit[i] = false; //未访问
}
}
//取最小（在未访问的结点中）
int GetMinInVisit()
{
int i, min = 0;
for (i = 0; i < length; i++)
{
//未访问
if (!visit[i])
{
//找到最小下标（不能是自身）
if (rootDist[min] > rootDist[i] || rootDist[min] == 0)
{
min = i;
}
}
}
return min;
}
//检查是否访问完毕
bool IsNull()
{
bool flag = true;
for (int i = 0; i < length; i++)
{
if (!visit[i]) //还有未访问的
flag = false;
}
return flag;
}
//迪杰斯特拉(Dikstra)算法（生成根到其他顶点的最短路径）
void Dijkstra(int index)
{
int i;
visit[index] = true; //标记访问
printf("%c %d\t", G.vertex[index], rootDist[index]);
//遍历中间结点的邻接结点，对比新旧距离
for (i = 0; i < length; i++)
{
//若 旧距离 > 新距离（改变新距离覆盖旧距离）
if (rootDist[i] > (rootDist[index] + G.weight[index][i]))
{
rootDist[i] = rootDist[index] + G.weight[index][i];
}
}
//退出判断
if (IsNull())
return;
index = GetMinInVisit(); //取出最小邻接结点，作为中间结点
Dijkstra(index); //递归调用Dijkstra()
}
//输出测试
void Print()
{
for (int i = 0; i < length; i++)
{
printf("\n%c结点邻接结点：\t", G.vertex[i]);
for (int j = 0; j < length; j++)
{
if (G.weight[i][j] != 0 && G.weight[i][j] != MAX) //有邻接结点
{
printf("%c %d\t", G.vertex[j], G.weight[i][j]);
}
}
}
}
int main()
{
InputVertex(); //输入顶点
GraphWeightInit(); //图权重初始化
CreateGraph(); //创建图
Init(); //初始化
Dijkstra(root); //迪杰斯特拉算法（先以根结点为中间结点遍历）（生成根到其他顶点的最短路径）
//Print(); //测试输出
return 0;
}三、弗洛伊德(Floyd)算法（多源最短路径）
优点：求所有顶点到所有顶点的最短路径。（多源最短路）
缺点：效率较低，时间复杂度为O(n^3)。
1、原理
基本思想：
不断找点进行中转，比较中转前后的最小距离。
原理：
最优子结构：图结构中一个显而易见的定理：最短路径的子路径仍然是最短路径 ,这个定理显而易见，比如一条从a到e的最短路径a->b->c->d->e 那么 a->b->c 一定是a到c的最短路径，c->d->e一定是c到e的最短路径，反过来，（原理）如果一条最短路必须要经过点k，那么i->k的最短路径+k->j的最短路径一定是i->j 经过k的最短路径，因此，最优子结构可以保证。
（左边矩阵是改进前的，右边矩阵是改进后的。）
弗洛伊德算法定义了两个二维矩阵：
D矩阵存放最小权(最短路径)，P矩阵存放最短前驱(中转点)
1、矩阵D记录顶点间的最小路径
例如D[1][2]= 3，说明顶点1 到 2 的最短路径为3；
2、矩阵P记录顶点间最小路径中的中转点
例如P[1][2]= 0 说明，1 到 2的最短路径轨迹为：1 -> 0 -> 2。
它通过3重循环，medium为中转点，begin为起点，end为终点，循环比较D[begin][end] 和 D[begin][medium] + D[medium][end] 之间的最小值，如果(D[begin][medium] + D[medium][end] )为更小值，则把(D[begin][medium] + D[medium][end] )覆盖保存在(D[begin][end])中。
2、存储
弗洛伊德算法定义了两个二维矩阵：
D矩阵存放最小权(最短路径)，P矩阵存放最短前驱(中转点)
思考：如果求任意两点之间的最短路径，两点之间可以直接到达但却不是最短的路径，要让任意两点（例如从顶点a点到顶点b）之间的路程变短，只能引入第三个点（顶点medium），并通过这个顶点medium中转即a->medium->b，才可能缩短原来从顶点a点到顶点b的路程。那么这个中转顶点medium是1~n中的哪个点呢？甚至有时候不只通过一个点，而是经过两个点或者更多中转点会更短。
下面给出一些例子深入理解一下：
例： 4 -> 3 一、直接：D[4][3] = 12 二、 过1：D[4][1]+D[1][3]=11
过1更短， 则D[4][3] = 11 且P[4][3] = P[4][1] = 1
例： 1 ->3 一、直接：D[1][3] = 6 二、过2：D[1][2]+D[2][3] = 5
过2更短， 则D[1][3] = 6 且P[1][3] = P[1][2] = 2
1、假如现在只允许经过1号顶点，求任意两点的最短路径我们应该怎么求呢？？
我们只需要判断 (D[begin][end]) 与 (D[begin][1] + D[1][end]) 的大小。（前者直接到达，后者经历中转）
//只经过1号中转顶点
for (begin = 1; begin <= n; begin++)
for (end = 1; end <= n; end++)
if (D[begin][end] > D[begin][1] + D[1][end])
D[begin][end] = D[begin][1] + D[1][end];在只允许经过1号中转顶点的情况下，任意两点之间的路程更新为：
2、继续求在只允许经过1和2号两个中转顶点的情况下任意两点之间的最短路程
//只经过1号中转顶点
for (begin = 1; begin <= n; begin++)
for (end = 1; end <= n; end++)
if (D[begin][end] > D[begin][1] + D[1][end])
D[begin][end] = D[begin][1] + D[1][end];
//只经过2号中转顶点
for (begin = 1; begin <= n; begin++)
for (end = 1; end <= n; end++)
if (D[begin][end] > D[begin][2] + D[2][end])
D[begin][end] = D[begin][2] + D[2][end];在只允许更新1号和2号顶点的情况下，任意两点之间的路径更新为：
3、..........继续往后，运行经过n个中转顶点（即全部）
//运行经过所有中转顶点
for(medium = 0; medium <= n; medium++)
for (begin = 1; begin <= n; begin++)
for (end = 1; end <= n; end++)
if (D[begin][end] > D[begin][medium] + D[medium][end])
D[begin][end] = D[begin][medium] + D[medium][end];允许经过所有中转顶点，最后的两点路径更新：
3、遍历
//遍历弗洛伊德算法
//确定begin -> end：从最近的前驱开始，一点一点往后追溯
void Traverse_Floyd()
{
int medium = 0;
for (int begin = 0; begin < length; begin++)
{
for (int end = 0; end < length; end++)
{
printf("\n%c", G.vertex[begin]);
medium = P[begin][end]; //开始追溯（此为最近的前驱）
while (medium != end) //未追溯到尾
{
printf("->%c", G.vertex[medium]); //打印中间结点
medium = P[medium][end]; //向后追溯
}
}
}
}4、代码
//弗洛伊德(Floyd)算法
/*测试案例
ABCDEFGHI
B 1 C 5
A 1 C 3 D 7 E 5
A 5 B 3 E 1 F 7
B 7 E 2 G 3
B 5 C 1 F 3 H 9 G 6 D 2
C 7 E 3 H 5
D 3 E 6 H 2 I 7
F 5 E 9 G 2 I 4
G 7 H 4
*/
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAXSIZE 20
#define MAX 65535 //代表无穷大
int length = 0; //顶点个数
int D[MAXSIZE][MAXSIZE]; //存放顶点之间的权
int P[MAXSIZE][MAXSIZE]; //存放顶点之间的前驱（中间结点）
//图（顶点和权）
typedef struct
{
char vertex[MAXSIZE];
int weight[MAXSIZE][MAXSIZE]; //权可以代替边（自身为0，相连有值，不相连无穷大）
}Graph;
Graph G;
//输入顶点
void InputVertex()
{
int i;
char ch;
printf("请输入图的顶点：\n");
scanf("%c", &ch);
for (i = 0; i < MAXSIZE && ch != '\n'; i++)
{
G.vertex[i] = ch;
scanf("%c", &ch);
}
length = i;
}
//图权重初始化
void GraphWeightInit()
{
int i, j;
for (i = 0; i < length; i++)
{
for (j = 0; j < length; j++)
{
if (i == j) //指向自己
G.weight[i][j] = 0;
else
G.weight[i][j] = MAX; //无穷大
}
}
}
//根据数据查找图顶点下标
int FindIndex(char ch)
{
int i;
for (i = 0; i < length; i++)
{
if (G.vertex[i] == ch)
return i;
}
return -1;
}
//创建图
void CreateGraph()
{
int i, j, index, weight;
char ch;
for (i = 0; i < length; i++)
{
printf("请输入%c的邻接顶点及权重（空格分隔，换行结束）：\n", G.vertex[i]);
scanf("%c", &ch);
while (ch != '\n')
{
while (ch == ' ') //为空格
{
scanf("%c", &ch); //输入字符
continue;
}
index = FindIndex(ch);
scanf("%d", &weight); //输入权重
while (weight == 32) //32为空格的ASCII码
{
scanf("%d", &weight);
continue;
}
G.weight[i][index] = weight; //存入权重
scanf("%c", &ch); //(下一轮)输入字符
}
}
}
//弗洛伊德算法
void Floyd()
{
int medium, begin, end;
//初始化矩阵
for (int i = 0; i < length; i++)
for (int j = 0; j < length; j++)
{
D[i][j] = G.weight[i][j];
P[i][j] = j;
}
//开始正式修改（最短路径及前驱）
for (medium = 0; medium < length; medium++) //中间结点
for (begin = 0; begin < length; begin++) //前驱结点
for (end = 0; end < length; end++) //后继结点
{
//经过中间结点路径更小，则1、需要覆盖掉原来的路径；2、替换掉前驱（中间结点）
if (D[begin][end] > (D[begin][medium] + D[medium][end]))
{
D[begin][end] = D[begin][medium] + D[medium][end]; //覆盖路径（只达标的话，只要这一句就够了）
P[begin][end] = P[begin][medium]; //更新前驱（中间结点）
//不能直接赋值medium：跨越结点之间的追溯，存放的是最近前驱，需要一个一个往后追溯
}
}
}
//测试矩阵输出
void PrintArray()
{
//遍历输出
printf("遍历输出D矩阵（最短路径）：\n");
for (int i = 0; i < length; i++)
{
printf("\n");
for (int j = 0; j < length; j++)
{
printf("%3d", D[i][j]);
}
}
printf("\n遍历输出P矩阵（前驱）：\n");
for (int i = 0; i < length; i++)
{
printf("\n");
for (int j = 0; j < length; j++)
{
printf("%3d", P[i][j]);
}
}
}
//遍历弗洛伊德算法
//确定begin -> end：从最近的前驱开始，一点一点往后追溯
void Traverse_Floyd()
{
int medium = 0;
for (int begin = 0; begin < length; begin++)
{
for (int end = 0; end < length; end++)
{
printf("\n%c", G.vertex[begin]);
medium = P[begin][end]; //开始追溯（此为最近的前驱）
while (medium != end) //未追溯到尾
{
printf("->%c", G.vertex[medium]); //打印中间结点
medium = P[medium][end]; //向后追溯
}
}
}
}
//输出测试
void Print()
{
for (int i = 0; i < length; i++)
{
printf("\n%c结点邻接结点：\t", G.vertex[i]);
for (int j = 0; j < length; j++)
{
if (G.weight[i][j] != 0 && G.weight[i][j] != MAX) //有邻接结点
{
printf("%c %d\t", G.vertex[j], G.weight[i][j]);
}
}
}
}
int main()
{
InputVertex(); //输入顶点
GraphWeightInit(); //图权重初始化
CreateGraph(); //创建图
Floyd(); //弗洛伊德算法（生成最短路径）
Traverse_Floyd(); //遍历弗洛伊德算法
//PrintArray(); //测试弗洛伊德矩阵输出
//Print(); //测试输出
return 0;
}
参考资料
《大话数据结构》
https://www.bilibili.com/video/BV1uX4y137Hf?from=search&seid=9442880507495572891
旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。
更多推荐
11
0- 0
已为社区贡献19条内容
所有评论(0)