海珠区专业做网站公司,优秀网页设计导航,wordpress+php调优,上海 网站设计公司负权图 此图用朴素迪氏或堆优化迪氏都会出错#xff0c;floyd可以处理。
负环图 但floyd无法处理负权环#xff0c;最短距离是无穷小。在环上不断循环。
经过k条边的最短距离#xff08;可能有负权变#xff09; 贝尔曼福特算法(bellman_ford)就是解决此问题的。 原理 …负权图 此图用朴素迪氏或堆优化迪氏都会出错floyd可以处理。
负环图 但floyd无法处理负权环最短距离是无穷小。在环上不断循环。
经过k条边的最短距离可能有负权变 贝尔曼福特算法(bellman_ford)就是解决此问题的。 原理
循环k次循环第i次时m_vDis表示各点最多经过i-1条边的最短距离vDis表示各点最多经过i条边的最短距离。
核心代码
templateconst int INF1000*1000*1000 class CBellMan { public: CBellMan(int n, const vectorvectorint edges,int s , int k ) { m_vDis.assign(n, INF); m_vDis[s] 0; for (int i 1; i k; i) { vectorint curDis m_vDis; for (const auto v : edges) { if (INF m_vDis[v[0]]) { continue; } curDis[v[1]] min(curDis[v[1]], m_vDis[v[0]] v[2]); } m_vDis.swap(curDis); } } vectorint m_vDis; };
测试样例
#include vector #includeassert.h using namespace std; int main() { const int INF 1000 * 1000 * 1000; vectorvectorint edges { {0,1,1},{1,2,2},{2,3,3},{3,0,-7} }; vectorvectorint results { {0,INF,INF,INF},{0,1,INF,INF},{0,1,3,INF},{0,1,3,6},{-1,1,3,6},{-1,0,3,6},{-1,0,2,6},{-1,0,2,5},{-2,0,2,5} }; for (int i 0; i results.size(); i) { CBellMan bm(4, edges, 0, i); for (int j 0; j 4; j) { assert(bm.m_vDis[j] results[i][j]); } } } 最短路径
最短路径就是经过“点数-1”条边的最短路径。如果没环这些边可以到达任意点。如果有正权环和0权环则拿掉这个环。如果负权环则最小距离是无穷小。下面来检测负权环。循环“点数-1”后再循环一次如果有点的最短距离变小则一定有负权环没负权环不会变短。如果有负权环则再循环一次一定有点任意负权环的负权边的终点距离变短。假定此点是e拿掉负权环上所有的边后源点到e的最短路径为Path。不拿掉负权环则e的最短路径为:Path此负权环。
核心代码
templateconst int INF1000*1000*1000 class CBellMan { public: CBellMan(int n, const vectorvectorint edges,int s , int k ) { m_vDis.assign(n, INF); m_vDis[s] 0; for (int i 1; i k; i) { vectorint curDis m_vDis; Do(edges, curDis); m_vDis.swap(curDis); } } bool Check(const vectorvectorint edges) { vectorint curDis m_vDis; Do(edges, curDis); for (int i 0; i curDis.size(); i) { if (m_vDis[i] ! curDis[i]) { return true; } } return false; } void Do(const std::vectorstd::vectorint edges, std::vectorint curDis) { for (const auto v : edges) { if (INF m_vDis[v[0]]) { continue; } curDis[v[1]] min(curDis[v[1]], m_vDis[v[0]] v[2]); } } vectorint m_vDis; }; 测试样例
#include vector #includeassert.h #include BellMan.h using namespace std; void Test1() { const int INF 1000 * 1000 * 1000; vectorvectorint edges { { 0,1,1 },{ 1,2,2 },{ 2,3,3 },{ 3,0,-7 } }; vectorvectorint results { { 0,INF,INF,INF },{ 0,1,INF,INF },{ 0,1,3,INF },{ 0,1,3,6 },{ -1,1,3,6 },{ -1,0,3,6 },{ -1,0,2,6 },{ -1,0,2,5 },{ -2,0,2,5 } }; for (int i 0; i results.size(); i) { CBellMan bm(4, edges, 0, i); for (int j 0; j 4; j) { assert(bm.m_vDis[j] results[i][j]); } } }
void Test2() { const int INF 1000 * 1000 * 1000; vectorvectorint edges { { 0,1,1 },{ 1,2,2 },{ 2,3,3 },{ 3,0,-7 } }; vectorint results { false,false,true }; for (int i 0; i 3; i) { edges[3][2] -5 - i; CBellMan bm(4, edges, 0, 3); assert(results[i] bm.Check(edges)); } } int main() { Test1(); Test2(); } 其它
测试环境
win7 VS2019 C17
相关下载
源码及测试用例https://download.csdn.net/download/he_zhidan/88393784doc版文档排版好https://download.csdn.net/download/he_zhidan/88348653
