朴素迪氏最短单源路径的原理及C++实现

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);
   }
}