谁能告诉我这到底叫迪杰斯特拉还是叫迪杰克斯特拉？？？
前言
周末(2019/2/23)，Payphone-X学完了唯一的多元最短路，现在，他开始向单元最短路进击啦（给自己一个小小的鼓励）
何为Dijkstra
先看看百度百科对于Dijkstra的解释
迪杰斯特拉算法是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。
——百度百科
……
先不看了……
度娘装高冷的毛病什么时候能改改啊……
还是看看通俗点的解释吧
在前边，我们已经学习了唯一的多元最短路，现在我们学习的Dijkstra是一种单元最短路算法。
（不知道啥是单元最短路的请自觉滚回Floyd）
时间复杂度为$O(n^2)$，比Floyd的暴力三循环快了好多的。
但要注意，Dijkstra只适用于没有负边权的情况。也就是说，如果图中有一条边的边权为负数，就不可以使用Dijkstra了。
Dijkstra的算法实现
在讲算法实现之前，先上一组数据。
5 6 // 5个点，6条边 |
把图建出来大概是这样的
现在我们开始讲Dijkstra的算法实现。
Dijkstra是一种类似于贪心的算法，步骤大概是下边这样：
1.选一个点做起始点。
2.遍历与起始点相连的所有边，寻找出一条最短的记录下来。
3.把这条边的另一个端点作为起始点，然后循环。
下面我们来用数据模拟一下。
首先，我们开一个number数组，用来存储1到点n的估计值。（说估计值是因为当前不一定是最短路，不理解的话一会就知道为什么了）
之后，我们用一个邻接矩阵map存储点i到j的距离，并把map的所有元素初始化为无穷大。
再定义一个start，表示下一个起始点，一个minn，表示下一个起始点到原点的最短距离。
先从1号点开始，得到map[1][2] = 4, map[1][4] = 1，则number[2] = 4, number[4] = 1，3与5两个点没有搜索到，不更新，还是无穷大。
很显然，现在的number数组还不是最终的答案。所以我们要进行第二次更新。
那……
为什么我们要把最短边的另一端点作为下一个起始点呐？
想想看，如果我们把另一端点作为下一次搜索的起始点，就可以得到每一个点到该点的最短路。再加上从这一个端点到初始点的最短路，就可以得到初始点到所有点的最短路啦
之后不断循环，直到循环过所有数据为止 （其实是作者太懒，不想推了）
最后答案是0 4 6 1 12
主体代码如下：void Dijkstra(int s){ //s为初始点编号
memset(number , 0x3f, sizeof(number)); //初始化估计值数组
int start = s; //从初始点搜索
bj[start] = true; //标记已被搜索
for(int i = 1; i <= n; i ++){
number[i] = min(number[i] , map[start][i]);//先更新一遍
}
for(int i = 1; i <= n - 1; i ++){
int minn = 9999999;
for(int j = 1; j <= n; j ++){
if(bj[j] == false && number[j] < minn){//找到最近的点，并记录编号，便于下次搜索。
minn = number[j];
start = j;
}
}
bj[start] = true; //注意这句话一定在for循环外，不然会有点搜不到
for(int j = 1; j <= n; j ++){
number[j] = min(number[j] , number[start] + map[start][j]);
} //最后更新一遍
}
}
是不是很简单吖（逃）
附件（Dijkstra模板，邻接矩阵实现）
|
