网站设置伪静态,电子商务主要学什么就业方向及前景,广州网站开发 找亦客公司优质,网站建设及代运营合同Dijkstra算法#xff0c;翻译为迪杰斯特拉或狄克斯特拉。在下驽钝#xff0c;记不住如此长的翻译#xff0c;故简称迪氏。
时间复杂度
O(n2)#xff0c;端点数的平方。
使用前提
边的权为正。可以非连通#xff0c;非连通的距离为-1。
原理
源点到源点的最短路径只有…Dijkstra算法翻译为迪杰斯特拉或狄克斯特拉。在下驽钝记不住如此长的翻译故简称迪氏。
时间复杂度
O(n2)端点数的平方。
使用前提
边的权为正。可以非连通非连通的距离为-1。
原理
源点到源点的最短路径只有一个节点{s}。除源点本身外其它端点的最短路径至少有两个端点整个路径{s...x2}可以拆分为两部分Path1{s...x1}和Path2{x2}。x2是最后节点且Path1就是s到x1的最短路径。假定Path3是s到x1的最短路径那Path3Path2比Path1Path2短与Path1Path2是最短路径矛盾。 按距离源点距离升序排序第i个端点(i0)的最短路径倒数第二个点一定取自[0,i)。x1不会等于x2否则直接丢掉最后的x2。假定x1的最短距离第m大mi。那{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 vectorvectorpairint, int vNeiB){m_vDis.assign(m_iSize, -1);m_vPre.assign(m_iSize, -1);vectorbool 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 vectorvectorint mat){m_vDis.assign(m_iSize, LLONG_MAX);m_vPre.assign(m_iSize, -1);vectorbool 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 vectorlong long DIS;const vectorint PRE;
private:const int m_iSize;vectorlong long m_vDis;//各点到起点的最短距离vectorint 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 vectorint vDis) { for (int i 0; i vDis.size(); i) { assert(vDis[i] DIS[i]); } } };
struct CDebugParam { int n; vectorvectorstd::pairint,int edges; int s; vectorint dis;//答案 };
int main() { vectorCDebugParam 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 C17
相关下载
源码及测试样例下载
朴素迪氏最短单源路径的原理及C源码及测试用例
【免费】朴素迪氏最短单源路径的原理及C源码及测试用例资源-CSDN文库
word版本讲解排版好
【免费】闻缺陷则喜之算法册C实现资源-CSDN文库
