朴素迪氏最短单源路径的原理及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 vectorint, 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 vectorint>>& 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
#include
#include
#include
using namespace std;

class CDebugN2Dis : public CN2Dis
{
public:
   using CN2Dis::CN2Dis;
   void Assert(const vector& vDis)
   {
       for (int i = 0; i < vDis.size(); i++)
       {
           assert(vDis[i] == DIS[i]);
       }
   }
};

struct CDebugParam
{
   int n;
   vector>> edges;
   int s;
   vector dis;//答案
};

int main()
{
   vector 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);
   }
}