前言
Dijkstra算法是应用于图中单源最短路径的搜索。我在这记录下我在学习该算法时的一些想法、理解与总结。首先我会写一段预备知识，以便于之后的理解。
算法基础
- 选择点到其他点的最短距离
- 局部最优是全局最优的充分必要条件
基础1：
在一张权值都是 同号 的图中，假设存在：①点A；②与A点相连的最短弧的弧头C；那么路径(A,C)为点A到点C的最短路径。
图1
如图所示，(A,C) 是点A到点C的最短路径。
解释：在权值都为正的情况下，没走一个点，其路径只会增加。所以与点A相接最短的弧是抵达弧头的最短路径。
正文
集合{S}：用来存放已寻找到最短路径的点。
集合{V}：全集
集合{V - S} 剩下的未找到最短路径的点集
如果集合{S}包括了所有的点，那么图的单源最短路径寻找结束。
算法开始的时候集合{S}中只包括原点，Dijkstra算法的过程是逐渐填充集合{S}的过程。
怎么填充？
在集合{V - S}中找一个距离{S}最近的点，命其为 点V 将其加入集合{S}中。
解释如图：
图2
注意：
①这张图和前面那张图没有任何联系；
②图中的虚线并不是真实存在的线，虚线上的数组不是点至原点的路径长度，而是集合{S}到点的路径长度，这些数值的需要计算；
在填充的过程中，会发现一个问题。每添加一个点之后，集合{S} 至集合{V - S}中点的最短距离可能会发生变化。
例如 图2 ：添加点C之后，集合{S}到点B的最短距离变为先经过点C，在到达点B。即 5+4 < 10。因此再每加入一个点后就要时刻更新集合{S} 至 集合{V - S}中点的最短距离。
总结：Dijkstra算法一共需要三步
- ① 创建集合{S}，将原点加入集合{S}。计算集合{S}到各点的距离，并储存。
- ② 寻找目前距离集合{S}最短距离的 点V ，将 点V 加入集合{S}
- ③ 更新集合{V - S} 中的点距离 集合{S} 的距离
应用
#define MAX_SIZE 100
int route[MAX_SIZE][MAX_SIZE];//路径
int curDis[MAX_SIZE];//当前最短路径
int pre[MAX_SIZE];//前驱
bool Set[MAX_SIZE];//集合{S}
int N;//结点个数
void shortestPath(const int start, const int dest)
{
//初始化
fill(Set, Set+N, false);
fill(curDis, curDis+N, INF);
int i;
for(i = 0 ; i < N ; i++) pre[i] = i;
curDis[start] = 0;
//遍历除原点外的顶点，因为每次循环都会寻找到一个可以加入集合{S}中的点，
for(i = 0 ; i < N ; i++){
//寻找 {V-S} 到原点最短路径的点
int v = -1, MIN = INF;
for(int j = 0 ; j < N ; j++){
if(!Set[j] && curDis[j] < MIN)
v = j;
min = curDis[j];
}
}
if(v == -1) break;//有些结点无法到达
Set[v] = true;
//更新 {V-S} 中的最短路径
for(int j = 0 ; j < N ; j++){
if(!Set[j] && route[u][j] != INF){
if(curDis[v] + route[v][j] < curDis[j]){
curDis[j] = curDis[v] + route[v][j];
pre[j] = u;//设置前驱
}else if(distance == shortestDistance[iY]){
//这里处理第二选择情况
}
}
}
}
}
注意：权值必须是全是正的，或者全是负的。两种情况的结果会不同，我只做在权值全为正的情况。如果想求最大路径，可以将正权值都制负，然后使用Dijkstra算法寻找最小值。然后再去绝对值，则是最大路径。
