单源点最短路径算法：Dijkstra算法
背景知识
图简介
图由节点和边组成，边有方向的图称为有向图，边没有方向的图称为无向图，最短路径算法里可以把无向图视为双向连接的有向图。 边有权重的图称为有权图，边没有权重的图称为无权图，无权图可以视为边的权重均为1的图。
单源点最短路径
给定图中的一个节点，求该节点到其他所有节点的最短路径。
Dijkstra算法
概述
Dijkstra属于单源点最短路径算法，时间复杂度为O(V^2)，适用于有权图、无权图、有向图、无向图（无权图视权为1，无向图视连接为双向连接），但是不适用于含负权边的图。通过分别以每个节点为源点，可以求图中所有节点两两之间的最短路径(和Floyd-Warshall算法功能相同）。
核心思想
Dijkstra属于贪心算法，算法通过构建最短路径树来求解，维护两个集合，集合V用来存储已经在最短路径树上的节点，集合U存储不在最短路径树上的节点，每次遍历V-U节点对(v,u)，寻找使得dis[v] + edge(v-u)最小的(v,u), v记录为u的前驱，dis[u] = dis[v] + edge(v-u).重复此过程，直到U为空
详细步骤
Step1：初始化，将源点加入集合V中，将其他节点加入集合U中，dis数组初始化为INT_MAX, dis[src] = 0; Step2：对V中的每个节点(v)：遍历集合U中的节点(u)，找到使dis[v] + edge(v-u)最小的(v-u)，执行v记录为u的前驱，dis[u] = dis[v] + edge(v-u)。 Step3：重复Step2，直到V为空，此时dis数组记录了每个节点距离源点的距离。
算法正确性证明
证明使用归纳法证明 Step1：n=1时，成立。集合V中第一个节点是源点，容易理解，第二个加入的节点肯定是距离源点最近的节点。 Step2：假设n=k-1时成立，下面使用反证法证明n=k时也成立。 ………………假设n=k时不成立，即对u，U集合中存在u2使得dis[u2] + edge(u2,u) < dis[v] + edge(v,u)。即存在dis[v2] + edge(v2-u2) + edge(u2,u) < dis[v] + edge(v,u)。那么可得dis[v2] + edge(v2-u2) < dis[v] + edge(v,u).由于dis[v] + edge(v,u)是我们找到的最小值，所以该等式显然不成立，所以n=k必然也是成立的，证明完毕。
为什么dijkstra不能适用于含负权边的图
因为存在负权边时，上述证明中的反证法就不能证伪了，如果edge(v2-u2)为负数，那么dis[v2] + edge(v2-u2) < dis[v] + edge(v,u)就有可能成立了。不好理解的话，可以把edge(v2-u2) 假定为非常小的负数，把edge(v,u) 假定为正数。
下面给出一个负权边的例子
可以看到dis[2] 应该为1，最短路径为0-1-2,但是dijkstra计算出来dis[2]为2，最短路劲为0-2.
C++实现：
#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
using namespace std;
class Solution
{
public:
vector<int> dijkstra(int src, vector<vector<int>> &graph, vector<int> &preNode)
{
///initialization
preNode = vector<int>(graph.size(), -1);
vector<int> distToSrc(graph.size());
unordered_set<int> visitedNodes;
unordered_set<int> unvisitedNodes;
for(int i = 0; i < graph.size(); i++)
{
unvisitedNodes.insert(i);
}
unvisitedNodes.erase(src);
visitedNodes.insert(src);
distToSrc[src] = 0;
preNode[src] = -1;
///do greedy, find most closed node each turn
while(!unvisitedNodes.empty())
{
int minNode = 0;
int previousNode = 0;
int minDistance = INT_MAX;
///traverse each v-u,v in visitedNodes, u in unvisitedNodes
for(auto vNode: visitedNodes)
{
for(auto unNode: unvisitedNodes)
{
if(graph[vNode][unNode] && distToSrc[vNode] + graph[vNode][unNode] < minDistance)
{
minDistance = distToSrc[vNode] + graph[vNode][unNode];
minNode = unNode;
previousNode = vNode;
}
}
}
visitedNodes.insert(minNode);
unvisitedNodes.erase(minNode);
distToSrc[minNode] = minDistance;
preNode[minNode] = previousNode;
}
return distToSrc;
}
int printPath()
{
vector<vector<int>> graph{{0, 4, 0, 0, 0, 0, 0, 8, 0},
{4, 0, 8, 0, 0, 0, 0, 11, 0},
{0, 8, 0, 7, 0, 4, 0, 0, 2},
{0, 0, 7, 0, 9, 14, 0, 0, 0},
{0, 0, 0, 9, 0, 10, 0, 0, 0},
{0, 0, 4, 14, 10, 0, 2, 0, 0},
{0, 0, 0, 0, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}};
vector<int> preNode;
auto dists = dijkstra(0, graph, preNode);
for(int i = 0; i < dists.size(); i++)
{
cout << i << " " << dists[i] << ": ";
int node = i;
stack<int> s;
while(node != -1)
{
s.push(node);
node = preNode[node];
}
while(!s.empty())
{
cout << s.top() << " ";
s.pop();
}
cout << endl;
}
return 0;
}
};
int main()
{
return Solution().printPath();
}