Dijkstra算法，翻译为迪杰斯特拉或狄克斯特拉。在下驽钝，记不住如此长的翻译，故简称迪氏。
时间复杂度
O(n2)，端点数的平方。
使用前提
边的权为正。可以非连通，非连通的距离为-1。
原理
源点到源点的最短路径只有一个节点{s}。除源点本身外，其它端点的最短路径至少有两个端点，整个路径{s...x2}可以拆分为两部分Path1={s...x1}和Path2={x2}。x2是最后节点，且Path1就是s到x1的最短路径。假定Path3是s到x1的最短路径，那Path3+Path2比Path1+Path2短，与Path1+Path2是最短路径矛盾。
按距离源点距离升序排序，第i个端点(i>0)的最短路径倒数第二个点一定取自[0,i)。x1不会等于x2，否则直接丢掉最后的x2。假定x1的最短距离第m大，m>i。那{s...x1}+{x2}显然比s{...x1}大，那么i > m，与m > i矛盾。
思路
两层循环，第一层循环依次处理，最短路径第i小的端点的最小路径。
第二层循环依次完成以下两个职责:
更新各点通过第i-1小端点到源点的距离。注意：已处理点，无需处理。如果距离变大无需处理。
求最短距离第i小的点。
m_vDis记录源点到各点的最短距离。
m_vPre记录各点最短路径的倒数第二个端点，方便获取最短路径。目的有二：一，增加理解性。二，某些场景会用到。
两个函数，分别通过邻接表和邻接矩阵获取最短路径。
核心代码
class CN2Dis
{
public:
CN2Dis(int iSize) :m_iSize(iSize), DIS(m_vDis), PRE(m_vPre)
{
}
void Cal(int start, const vector<vector<pair<int, int>>>& vNeiB)
{
m_vDis.assign(m_iSize, -1);
m_vPre.assign(m_iSize, -1);
vector<bool> vDo(m_iSize);//点是否已处理
auto AddNode = [&](int iNode)
{
//const int iPreNode = m_vPre[iNode];
long long llPreDis = m_vDis[iNode];
vDo[iNode] = true;
for (const auto& it : vNeiB[iNode])
{
if (vDo[it.first])
{
continue;
}
if ((-1 == m_vDis[it.first]) || (it.second + llPreDis < m_vDis[it.first]))
{
m_vDis[it.first] = it.second + llPreDis;
m_vPre[it.first] = iNode;
}
}
long long llMinDis = LLONG_MAX;
int iMinIndex = -1;
for (int i = 0; i < m_vDis.size(); i++)
{
if (vDo[i])
{
continue;
}
if (-1 == m_vDis[i])
{
continue;
}
if (m_vDis[i] < llMinDis)
{
iMinIndex = i;
llMinDis = m_vDis[i];
}
}
return (LLONG_MAX == llMinDis) ? -1 : iMinIndex;
};
int next = start;
m_vDis[start] = 0;
while (-1 != (next = AddNode(next)));
}
void Cal(int start, const vector<vector<int>>& mat)
{
m_vDis.assign(m_iSize, LLONG_MAX);
m_vPre.assign(m_iSize, -1);
vector<bool> vDo(m_iSize);//点是否已处理
auto AddNode = [&](int iNode)
{
long long llPreDis = m_vDis[iNode];
vDo[iNode] = true;
for (int i = 0; i < m_iSize; i++)
{
if (vDo[i])
{
continue;
}
const long long llCurDis = mat[iNode][i];
if (llCurDis <= 0)
{
continue;
}
m_vDis[i] = min(m_vDis[i], m_vDis[iNode] + llCurDis);
}
long long llMinDis = LLONG_MAX;
int iMinIndex = -1;
for (int i = 0; i < m_iSize; i++)
{
if (vDo[i])
{
continue;
}
if (m_vDis[i] < llMinDis)
{
iMinIndex = i;
llMinDis = m_vDis[i];
}
}
if (LLONG_MAX == llMinDis)
{
return -1;
}
m_vPre[iMinIndex] = iNode;
return iMinIndex;
};
int next = start;
m_vDis[start] = 0;
while (-1 != (next = AddNode(next)));
}
const vector<long long>& DIS;
const vector<int>& PRE;
private:
const int m_iSize;
vector<long long> m_vDis;//各点到起点的最短距离
vector<int> m_vPre;//最短路径的前一点
};测试用例
#include <iostream>
#include <vector>
#include <queue>
#include <assert.h>
using namespace std;
class CDebugN2Dis : public CN2Dis
{
public:
using CN2Dis::CN2Dis;
void Assert(const vector<int>& vDis)
{
for (int i = 0; i < vDis.size(); i++)
{
assert(vDis[i] == DIS[i]);
}
}
};
struct CDebugParam
{
int n;
vector<vector<std::pair<int,int>>> edges;
int s;
vector<int> dis;//答案
};
int main()
{
vector<CDebugParam> params = { {1,{{}},0,{0}},
{2,{{}},0,{0,-1}},{2,{{{1,2}},{{0,2}}},0,{0,2} }
,{3,{{{1,4},{2,5}},{{0,4}},{{0,5}}},0,{0,4,5} }
,{3,{{{1,4},{2,8}},{{0,4},{2,3}},{{0,8},{1,3}}},0,{0,4,7} }
,{3,{{{1,4},{2,8}},{{0,4},{2,5}},{{0,8},{1,5}}},0,{0,4,8} }
};
for (const auto& par : params)
{
CDebugN2Dis n2Dis(par.n);
n2Dis.Cal(par.s, par.edges);
n2Dis.Assert(par.dis);
}
}
