【干货满满！】【最小生成树】Prim算法
【最小生成树】Kruskal算法
目录
前言
一、最短路径的概念及应用
二、Dijkstra迪杰斯特拉
1.什么是Dijkstra
2.逻辑实现
总结
无论是什么程序都要和数据打交道，一个好的程序员会选择更优的数据结构来更好的解决问题，因此数据结构的重要性不言而喻。数据结构的学习本质上是让我们能见到很多前辈在解决一些要求时间和空间的难点问题上设计出的一系列解决方法，我们可以在今后借鉴这些方法，也可以根据这些方法在遇到具体的新问题时提出自己的解决方法。（所以各种定义等字眼就不用过度深究啦，每个人的表达方式不一样而已），在此以下的所有代码都是仅供参考，并不是唯一的答案，只要逻辑上能行的通，写出来的代码能达到相同的结果，并且在复杂度上差不多，就行了。
在介绍最短路径之前我们首先要明白两个概念：什么是源点，什么是终点？在一条路径中，起始的第一个节点叫做源点；终点：在一条路径中，最后一个的节点叫做终点；注意！源点和终点都只是相对于一条路径而言，每一条路径都会有相同或者不相同的源点和终点。
而最短路径这个词不用过多解释，就是其字面意思：在图中，对于非带权无向图而言，从源点到终点边最少的路径（也就是BFS广度优先的方法）；而对于带权图而言，从源点到终点权值之和最少的路径叫最短路径；
最短路径应用：道路规划；
我们最关心的就是如何用代码去实现寻找最短路径，通过实现最短路径有两种算法：Dijkstra迪杰斯特拉算法和Floyd弗洛伊德算法，接下来我会详细讲解Dijkstra迪杰斯特拉算法；
Dijkstra迪杰斯特拉是一种处理单源点的最短路径算法，就是说求从某一个节点到其他所有节点的最短路径就是Dijkstra；
在Dijkstra中，我们需要引入一个辅助变量D（遇到解决不了的问题就加变量[_doge]），这个D我们把它设置为数组，数组里每一个数据表示当前所找到的从源点V开始到每一个节点Vi的最短路径长度，如果V到Vi有弧，那么就是每一个数据存储的就是弧的权值之和，否则就是无穷大；
我们还需要两个数组P和Final，它们分别表示：源点到Vi的走过的路径向量，和当前已经求得的从源点到Vi的最短路径（也就是作为一个标记表示该节点已经加入到最短路径中了）；
那么对于如下这个带权无向图而言，我们应该如何去找到从V0到V8的最短路径呢；
在上文中我们已经描述过了，在从V0到V8的这一条最短路径中，V0自然是源点，而V8自然是终点；于是我根据上文的描述具现化出如下的表格；
在辅助向量D中，与源点V0有边的就填入边的权值，没边就是无穷大；
构建了D、P和Final，那么我们要开始遍历V0，找V0的所有边中权值最短的的边，把它在D、P、Final中更新；
具体是什么意识呢？在上述带权无向图中，我们可以得到与源点有关的边有（V0，V1）和（V0，V2），它们的权值分别是1和5，那么我们要找到的权值最短的的边，就是权值为1 的（V0，V1），所以把Final[1]置1，表示这个边已经加入到最短路径之中了；
而原本从V0到V2的距离是5，现在找到了一条更短的从V0 -> V1 -> V2距离为4，所以D[2]更新为4，P[2]更新为1，表示源点到V2经过了V1的中转；
继续遍历，找到从V0出发，路径最短并且final的值为0的节点。因为经过节点V1的中转，源点到V3和V4有了路径，从源点到V3的距离是1+7==8，到V4的距离是1+5==6，把它们在D中更新；再以V1为中心，去找与V1有关的边中权值最短的边，可以得到此时V0到V2的距离为4，是我们要找的边，于是把V2加入到最短路径中；
重复上述步骤，遍历以V2为中心的顶点，与V2有关的顶点有V0、V1、V4、V5，其中0和1已经加入到最短路径中了所以不管它们，而V2到V4的路径最短，所以将Final[4]置1；那么V0到V4原来的距离是6，而现在经过V2的中转，V0到V1到V2到V4的距离为5，所以更新D、P；
接着找以V4为中心，与V4有关的边：V3、 V5、V6、 V7更新D、P，原本V0到V3是距离8，现在是更新为7，且我们可以发现这条边的权值最小，所以把Final[3]置1；
现在V3最短，所以以V3为中心，到V6的距离最近，所以更新D[6]、P[6]和Final[6]；
现在V6最短，所以以V6为中心，到V7的距离最近，所以更新D[7]、P[7]和Final[7]；
现在V7最短，所以以V7为中心，到V8的距离最近，所以更新D[8]、P[8]和Final[8]；
至此，源点和终点都被加入到了最短路径当中，Dijkstra算法结束；那么我们从P[8]开始从后往前推，就可以得到这个带权无向图的从V0到V8的最短路径；
如图所示从P[8]开始从后往前推算，数组P中的值就是在最短路径中该节点的上一个节点；可以得到：V8<-V7<-V6<-V3<-V4<-V2<-V1<-V0；即如下图所示：
3.代码实现
逻辑上理顺了，那么问题来了，代码要怎么写？因为是带权的无向图，所以这里我们还是以邻接矩阵去构建图（关于邻接矩阵的详细概念在我往前的文章里有），这里还是简单说一下，如果Vi到Vj有边，那么存入的就是这条边的权值，如果没有边就存入一个不可能的数表示无穷大（如65535）
void creategrahp(AdjMatrix* G)
{
int n, e;//n代表顶点数 e代表边数
int vi, vj;//vi vj代表边的两个顶点对
int w;//表示边的权值
printf("要输入的顶点数和边数\n");
scanf("%d%d",&n,&e);
G->numV = n;
G->numE = e;
//图的初始化
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
{
//一个非带权的图 0代表没有边 1代表有边
//边不指向自己 即对角线为0
G->Edge[i][j] = 0;
}
else
{
//如果是带权的图 初始化为0或者为一个不可能的值
G->Edge[i][j] = 65535;
}
}
}
//将顶点存入数组
for(int i = 0; i < G->numV; i++)
{
printf("请输入第%d个节点的信息\n",i + 1);
scanf("%d", &G->Vertices[i]);
}
//输入边的信息
for(int i = 0; i< G->numE; i++)
{
//如果输入的是顶点的值 需要从顶点集中查找对应的下标
//如果是带权图 还要输入权的信息
printf("请输入边的信息Vi,Vj和权值w\n");
scanf("%d%d%d",&vi,&vj,&w);
G->Edge[vi][vj] = w;
//如果是带权图 等于权值
//如果是有向图 就不对称
//如果是无向图 矩阵对称
G->Edge[vj][vi] = w;
}
}至于Dijkstra的代码实现也很简单，只要按照上文中逻辑去实现就可以了；我每一步代码都详细写了注释，如果还有不清楚的可以私信问我；
首先我们要初始化D、P和Final；D初始存入与源点有关的边的权值；P一开始可以初始化为0或-1表示没有路径；Final初始化为0表示没有被加入到最短路径的标志；
void ShortPath_Dijkstra(AdjMatrix* G, int v0, P* p, D* d)
{
int k;//记录当前最短路径的下标
int final[200];//final[x] = 1 表示已求得的到v0的最短路径
//初始化DPFinal
for(int i = 0; i < G->numV; i++)
{
final[i] = 0;//初始化为未知状态
(*d)[i] = G->Edge[v0][i];//如果v0传进的是值 寻找下标
(*p)[i] = -1;
}
final[v0] = 1;
(*d)[v0] = 0;//自己到自己的路径为0接下来就是找权值最短的边；用变量K记录找到的边最小的顶点的下标；
//主循环 求每次v0到v的最短路径
for(int i = 1; i < G->numV; i++)
{
int min = 65535;
//寻找与v0距离最近的顶点
for(int j = 0; j < G->numV; j++)
{
if(final[j] != 1 && (*d)[j] < min)
{
min = (*d)[j];
k = j;
}
}
//把Vk加入到最短路径中
final[k] = 1;然后以K为中转，找以K为中心的邻接点到源点的距离，如果这个距离小于原来的距离那么更新D和P；如此循环直到所有的点都被加入到了最短路径中，结束！
//修正当前最短路径的距离
//以Vk作为中转，更新以Vk为中心的邻接点到V0的距离
for(int j = 0; j < G->numV; j++)
{
//如果当前找到v的顶点的路径小于原来的路径长度
if(min + G->Edge[k][j] < (*d)[j] && final[j] != 1)
{
//说明找到了更短的路径 修改DP
(*d)[j] = min + G->Edge[k][j];
(*p)[j] = k;
}
}
全部代码
#include<stdio.h>
#include<stdlib.h>
//最短路径算法 迪杰斯特拉 求有向图G 从某一个顶点开始 到其余各个顶点的最短路径P以及带权长度
//P为前驱顶点的下标 D为从选取的顶点V0到V顶点的最短路径长度
typedef int P[200];//储存最短路径下标
typedef int D[200];//v0到v的最短路径长度和
//邻接矩阵
typedef struct AdjacentMatrix
{
//顶点集
int Vertices[200];
//边集
int Edge[200][200];
//顶点数 边数
int numV, numE;
}AdjMatrix;
void creategrahp(AdjMatrix* G)
{
int n, e;//n代表顶点数 e代表边数
int vi, vj;//vi vj代表边的两个顶点对
int w;//表示边的权值
printf("要输入的顶点数和边数\n");
scanf("%d%d",&n,&e);
G->numV = n;
G->numE = e;
//图的初始化
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(i == j)
{
//一个非带权的图 0代表没有边 1代表有边
//边不指向自己 即对角线为0
G->Edge[i][j] = 0;
}
else
{
//如果是带权的图 初始化为0或者为一个不可能的值
G->Edge[i][j] = 65535;
}
}
}
//将顶点存入数组
for(int i = 0; i < G->numV; i++)
{
printf("请输入第%d个节点的信息\n",i + 1);
scanf("%d", &G->Vertices[i]);
}
//输入边的信息
for(int i = 0; i< G->numE; i++)
{
//如果输入的是顶点的值 需要从顶点集中查找对应的下标
//如果是带权图 还要输入权的信息
printf("请输入边的信息Vi,Vj和权值w\n");
scanf("%d%d%d",&vi,&vj,&w);
G->Edge[vi][vj] = w;
//如果是带权图 等于权值
//如果是有向图 就不对称
//如果是无向图 矩阵对称
G->Edge[vj][vi] = w;
}
}
void ShortPath_Dijkstra(AdjMatrix* G, int v0, P* p, D* d)
{
int k;//记录当前最短路径的下标
int final[200];//final[x] = 1 表示已求得的到v0的最短路径
//初始化DPFinal
for(int i = 0; i < G->numV; i++)
{
final[i] = 0;//初始化为未知状态
(*d)[i] = G->Edge[v0][i];//如果v0传进的是值 寻找下标
(*p)[i] = -1;
}
final[v0] = 1;
(*d)[v0] = 0;//自己到自己的路径为0
//主循环 求每次v0到v的最短路径
for(int i = 1; i < G->numV; i++)
{
int min = 65535;
//寻找与v0距离最近的顶点
for(int j = 0; j < G->numV; j++)
{
if(final[j] != 1 && (*d)[j] < min)
{
min = (*d)[j];
k = j;
}
}
//把Vk加入到最短路径中
final[k] = 1;
//修正当前最短路径的距离
//以Vk作为中转，更新以Vk为中心的邻接点到V0的距离
for(int j = 0; j < G->numV; j++)
{
//如果当前找到v的顶点的路径小于原来的路径长度
if(min + G->Edge[k][j] < (*d)[j] && final[j] != 1)
{
//说明找到了更短的路径 修改DP
(*d)[j] = min + G->Edge[k][j];
(*p)[j] = k;
}
}
}
}
int main()
{
AdjMatrix* G = (AdjMatrix*)malloc(sizeof(AdjMatrix));
int p[200];
int d[200];
creategrahp(G);
int v0 = 0;
ShortPath_Dijkstra(G, v0, &p, &d);
for (int i = 1; i < G->numV; i++)
{
printf("v%d - v%d:", v0, i);
int j = i;
while (p[j] != -1)
{
printf("%d", p[j]);
j = p[j];
}
printf("\n");
}
printf("最短路径长度");
for (int i = 1; i < G->numV; i++)
{
printf("v%d-v%d : %d\n", G->Vertices[0], G->Vertices[i], d[i]);
}
system("pause");
return 0;
}需要注意的是：DIjkstra迪杰斯特拉算法只能找从某一个顶点开始，到其余各个顶点的最短路径P以及带权长度；那么如果我想要知道任意两个节点之间的最短路径要怎么办呢？大家可以思考一下，我们下期再讲~