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++源码及测试用例资源-CSDN文库
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
