单源最短路径之迪杰斯特拉算法
在前面的文章中，对于图的构建以及广搜和深搜有了介绍，今天就带来一个新的知识点，即最短路径问题。最短路径问题是图论研究中的一个经典算法问题， 旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
迪杰斯特拉算法
迪杰斯特拉(Dijkstra)算法解决最短路径问题，其创造者：艾兹格·W·迪科斯彻 （Edsger Wybe Dijkstra）。
Dijkstra算法是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
Dijkstra算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
迪杰斯特拉算法属于贪婪算法的应用，基本思想为：
保证每个阶段选取到的顶点到起始点的路径长度都是最短的。在这种情况下，迪杰斯特拉算法只需要不断计算更新选取的顶点到其邻接顶点的路径长度就可以了，这对于路径长度必然是递增的（无权或非负权）图来说， 是没有问题的，因为，对于它们来说，每一步的最优解就是整体的最优解。
然而，对于 负权图 来说，就不是这样的了，负权的存在，会导致一种情况的发生：
v0->v1 权值3
v0->v2 权值2
v1->v2 权值-1那么以v0为起点时，Dijkstra算法得到最短路径为
v0->v1 3
v0->v2 2实际上，最短路径
v0->v2->v1 2
v0->v2 2实现过程
单源最短路径
首先对于源点本身，其最短距离为0，然后源点可以直达(不需要其他顶点作为中介)的顶点，其最短距离是权值本身(负权图除外)， 不可直达的顶点，其权值等于源点到中介顶点的距离+中介顶点到目标顶点的距离(如果发现更短的权值，则替代)，所以建立两个 数组，一个保存最短路径 s[]，一个保存是否已经走过 vis[]。
V0->V1 的权值为1
V0->V2 的权值为3
V1->V3 的权值为1
V2->V3 的权值为1如果以V0作为起点，首先s[]初始值设为INT_MAX，然后将V0的最短路径s[0]设置0。
第一步:遍历所有顶点(用u表示),如果顶点u未走过，且s[u]<INT_MAX 则说明目前距离起点最近的顶点就是u。第一轮遍历最小值就是起点V0，因为上面将s[0]设置为0
第二步:对第一步得到的顶点u，将其设置为走过，vis[u] = 1 ,然后获取u可达的顶点，重制他们的最短路径。也就是V1和V2需要重置最短距离。目的s[1]和s[2]为INT_MAX，新的 s[1] = s[0]+1 (1是上面规定V0->V1的权值) s[2] = s[0]+3 (3是上面规定V0->V2的权值) 新旧比较，发现新的小于旧的值，那么替换s[1]和s[2].如果大于则无视。
第三步:使用第一步的逻辑，再次遍历。第二轮遍历最小值是V1 因为s[1]<s[2] 且 vis[1] 没有走过
第四步:使用第二步逻辑，得到u=1,其可达顶点为V3，此时V3的最短距离为INT_MAX ,新的最短距离s[3] = s[1]+1(1是上面规定V1->V3的权值)， 那么s[3]被重置为2。
第五步:继续按照第一步的逻辑遍历，目前最短距离，且没有走的顶点是V3。
第六步:按照第二步的逻辑，找到V3可达顶点，发现没有V3可达的顶点，则无视
第七步:再次按照第一步的逻辑遍历，目前最短距离，且没有走的顶点是V2。
第八步:按照第二步的逻辑，找到V2可达顶点，为V3，此时旧的s[3]为2，新的s[3] = s[2]+1 = 4. 因为新的s[3]>旧的s[3]，那么无需考虑
第九步，结束，目前s[] = {0,1,3,2}。
上面推导步骤有些多，但是实际上总是在重复第一步和第二步，就是遍历顶点个数次，每次松弛顶点的权值。
注:
对于负权图无效是因为在某个顶点局部最优的时候，可能其他边因为负权的情况，导致最终顶点不是最优路径
实现代码(C++)
//
// main.cpp
// Dijkstra
//
// Created by 陈龙
// Copyright © 2019 陈龙. All rights reserved.
//
#include <iostream>
#include <vector>
using namespace std;
//顶点
const int N = 6;
//结构体
struct Graph{
//顶点
int v;
//边权
int w;
Graph(int _v,int _w):v(_v),w(_w){};
};
//邻接表
vector<Graph> ver[N];
//是否遍历
int vis[N];
//最短路径
int S[N];
//初始化
void init(){
//将路径长度存入S，如果不可达，则无穷大
int MAX=INT_MAX;
//遍历顶点，初始化S
for (int i=0; i<N; i++) {
S[i]=MAX;
}
}
//单源最短路径
void Dijkstra(int v){
//可达节点进行初始化
for(int i=0;i<ver[v].size();i++){
Graph g = ver[v][i];
S[g.v] = g.w;
}
//源节点本身距离为0
S[v] = 0;
//已经遍历过
vis[v] = 1;
//每一个节点进行遍历
for(int i=0;i<N;i++){
int u = -1;
int min = INT_MAX;
//对于可达节点，找到其最短路径的顶点
for (int j=0;j<N; j++) {
if(vis[j]==0 && S[j]<min){
min = S[j];
u = j;
}
}
//已经遍历过
vis[u]=1;
if (u==-1) {//无可达节点或者没有最短路径
return;
}
//可达最短路径
for (int j=0; j<ver[u].size(); j++) {
Graph g = ver[u][j];
if (S[g.v] > S[u] + g.w ) {
S[g.v] =S[u] + g.w ;
}
}
}
}
int main(int argc, const char * argv[]) {
// insert code here...
init();
for (int i=0; i<N; i++) {
cout<<S[i]<<endl;
}
ver[0].push_back(Graph(1,1));
ver[0].push_back(Graph(2,3));
ver[1].push_back(Graph(3,4));
ver[2].push_back(Graph(3,1));
ver[2].push_back(Graph(4,5));
ver[3].push_back(Graph(5,7));
Dijkstra(0);
for (int i=0; i<N; i++) {
cout<<S[i]<<endl;
}
return 0;
}腾讯云开发者
