目录

一、最短路径概念

二、迪杰斯特拉(Dijkstra)算法（单源最短路径）

1、原理

2、过程

3、代码

三、弗洛伊德(Floyd)算法（多源最短路径）

1、原理

2、存储

3、遍历

4、代码

参考资料

一、最短路径概念

最短路径，顾名思义，两结点之间最短的路径（可以是非邻接结点）。

最小生成树和最短路径区别：

最小生成树：连通图的最短路径。

最短路径：两任意结点之间（可以非邻接）的最短路径。

二、迪杰斯特拉(Dijkstra)算法（单源最短路径）

优点：效率较高，时间复杂度为O(n^2)。

缺点：只能求一个顶点到所有顶点的最短路径。 （单源最短路）

1、原理

1、先选定一个根结点，并选定一个数组，先确定未遍历前的初始距离，把距离最短的邻接结点选定为中间结点，并标记访问过，开始往下遍历，挨个访问那个中间结点的邻接结点。计算出根结点到中间结点+中间结点到新邻接结点的距离，作为新距离，对比新距离和旧距离，如果新距离大，则把新距离替换掉旧距离，否则不变。

2、一轮访问结束后，从未标记的结点中选定距离最短的，把它作为中间结点，继续往下访问。若都标记过，则算法结束。

2、过程

1、保存根结点及到其他结点的权（距离）

2、访问最近结点作为中间结点

3、对比新距离（根结点到中间结点+中间结点到新结点）和旧距离（根结点直接到新结点）

4、若新距离短，修改保存到数组

5、继续访问后面的，把未访问的距离根最近结点作为中间结点，继续访问它的邻接结点

6、继续对比新距离和旧距离

7、若新距离短，则修改保存到数组

8、继续以距离根结点最短的结点为对象，访问它的邻接结点

9、全部访问完毕，结束算法

欣赏一下自己的稿书：

3、代码

//迪杰斯特拉(Dijkstra)算法/*测试案例ABCDEFGHIB 1 C 5A 1 C 3 D 7 E 5A 5 B 3 E 1 F 7B 7 E 2 G 3B 5 C 1 F 3 H 9 G 6 D 2C 7 E 3 H 5D 3 E 6 H 2 I 7F 5 E 9 G 2 I 4G 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;elseG.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)算法/*测试案例ABCDEFGHIB 1 C 5A 1 C 3 D 7 E 5A 5 B 3 E 1 F 7B 7 E 2 G 3B 5 C 1 F 3 H 9 G 6 D 2C 7 E 3 H 5D 3 E 6 H 2 I 7F 5 E 9 G 2 I 4G 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;elseG.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;}

参考资料

《大话数据结构》

/video/BV1uX4y137Hf?from=search&seid=9442880507495572891

/jeffleo/article/details/53349825?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%25220713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-53349825.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

/yuewenyao/article/details/81021319?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522162842804216780271587280%2522%252C%2522scm%2522%253A%25220713.130102334..%2522%257D&request_id=162842804216780271587280&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-81021319.pc_search_result_control_group&utm_term=%E5%BC%97%E6%B4%9B%E4%BC%8A%E5%BE%B7%E7%AE%97%E6%B3%95&spm=1018.2226.3001.4187

/p/33162490