朴素迪氏最短单源路径的原理及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);
     }
 }

测试环境

win10  VS2022  C++17

相关下载

源码及测试样例下载：

朴素迪氏最短单源路径的原理及C++源码及测试用例

【免费】朴素迪氏最短单源路径的原理及C++源码及测试用例

word版本讲解排版好

【免费】闻缺陷则喜之算法册C++实现资源