首页 > 编程语言 >多源最短路径的原理及C++实现

多源最短路径的原理及C++实现

时间:2023-10-19 12:06:12浏览次数:28  
标签:路径 i1 i2 C++ int vector vMat INF 多源


时间复杂度

O(n3),n是端点数。

核心代码

template<class T, T INF = 1000 * 1000 * 1000>
 class CNeiBoMat
 {
 public:
   CNeiBoMat(int n, const vector<vector<int>>& edges,bool bDirect=false,bool b1Base= false)
   {
     m_vMat.assign(n, vector<int>(n, INF));
     for (int i = 0; i < n; i++)
     {
       m_vMat[i][i] = 0;
     }
     for (const auto& v : edges)
     {
       m_vMat[v[0]- b1Base][v[1]- b1Base] = v[2];
       if (!bDirect)
       {
         m_vMat[v[1]- b1Base][v[0]- b1Base] = v[2];
       }
     }
   }
   vector<vector<int>> m_vMat;
 };//多源码路径
 template<class T,T INF = 1000*1000*1000>
 class CFloyd
 {
 public:
   CFloyd(const  vector<vector<T>>& mat)
   {
     m_vMat = mat;
     const int n = mat.size();
     for (int i = 0; i < n; i++)
     {//通过i中转
       for (int i1 = 0; i1 < n; i1++)
       {
         for (int i2 = 0; i2 < n; i2++)
         {
           //此时:m_vMat[i1][i2] 表示通过[0,i)中转的最短距离
           m_vMat[i1][i2] = min(m_vMat[i1][i2], m_vMat[i1][i] + m_vMat[i][i2]);
           //m_vMat[i1][i2] 表示通过[0,i]中转的最短距离
         }
       }
     }   
   };
   vector<vector<T>> m_vMat;
 };

原理

当一层循环执行完后,m_vMat[i1][i2]表示经过[0,i)中的任意个点的最短距离。
初始状态下, m_vMat[i1][i2]表示直达的最小距离,也就是经过0个点。
通过[0,i)中任意个点,i1到i2的最短路径记为PrePathi1i2,通过[0,i+1)中任意个点,i1到i2的距离的路径为Pathi1i2,如果Path不经过Pathi1i2,则和PrePathi1i2相同。如果经过则可以拆分成{i1…i}+{i…i2},显然{i1…i}是PrePathi1i,{i…i2}是PrePathii2,否则替换成PrePathi1i和PrePathii2。
m_vMat同时表示PreMath和Math,如果m_vMat[i1][i]或m_vMat[i][i2]已经更新,会带来错误的结果么?结果是不会,会更新但值不变。
当i1等于i时:
m_vMat[i][i2] = min(…, m_vMat[i][i] + m_vMat[i][i2]);
由于m_vMat[i][i]为0,所以右式就是左式。
当i2等于i时,类似。

样例
 

多源最短路径的原理及C++实现_多源最短路径


假定有5个点,前4个点连通。整个处理流程如下:

初始状态


处理完i等于0(不变)

0

1

4

INF

INF

1

0

2

4

INF

4

2

0

3

INF

INF

4

3

0

INF

INF

INF

INF

INF

0



处理完i等于1

处理完i等于2(不变)



3

5







3





5










处理完i等于3,结果不变

最终结果

0

1

3

5

INF

1

0

2

4

INF

3

2

0

3

INF

5

4

3

0

INF

INF

INF

INF

INF

0

测试样例

#include <vector>
 #include<assert.h>
 using namespace std;struct CDebugParam
 {
     int n;
     vector<vector<int>> edges;
     vector<vector<int>> result;
 };int main()
 {
     const int INF = 1000 * 1000 * 1000;
     vector<CDebugParam> params = { {5,{{0,1,1},{0,2,4},{1,2,2},{1,3,4},{2,3,3}},
         {
             {0,1,3,5,INF},
             {1,0,2,4,INF},
             {3,2,0,3,INF},
             {5,4,3,0,INF},
             {INF,INF,INF,INF,0}
         }
         } };
     for (const auto& param : params)
     {
         CNeiBoMat<int> mo(param.n, param.edges);
         CFloyd<int> floyd(mo.m_vMat);
         for (int r = 0; r < param.n; r++)
         {
             for (int c = 0; c < param.n; c++)
             {
                 assert(param.result[r][c] == floyd.m_vMat[r][c]);
             }
         }
     }
 }

其它

测试环境

win7 VS2019 C++17

源码及测试样例下载


doc文档下载


标签:路径,i1,i2,C++,int,vector,vMat,INF,多源
From: https://blog.51cto.com/u_15724537/7934067

相关文章

  • 存在负权边的单源最短路径的原理和C++实现
    负权图此图用朴素迪氏或堆优化迪氏都会出错,floyd可以处理。负环图 但floyd无法处理负权环,最短距离是无穷小。在环上不断循环。经过k条边的最短距离(可能有负权变)贝尔曼福特算法(bellman_ford)就是解决此问题的。原理循环k次,循环第i次时,m_vDis表示各点最多经过i-1条边的最短距离;v......
  • 堆优化迪氏最短单源路径原理及C++实现
    时间复杂度O(ElogE),E是边数。适用与稀疏图。使用前提边的权为正。可以非连通,非连通的距离为-1。原理优选队列(小根堆)记录两个数据:当前点到源点距离,当前点。先处理距离小的点;如果距离相等,先处理谁都可以。可以用pair记录,不用重写小于。优先队列只记录如下情况的距离:一,{0,源点}。二,......
  • 有向图计数优化版原理及C++实现
    题目见前面章节。有向图访问计数的原理及C++实现第一版不需要拓扑排序,也不需要并集查找,直接dfs了。完成以下三个职责:一,DFS那些端点在环上。二,DFS环上各点此环的长度。三,DFS非环上各点。分析cur是当前dfs的节点,next为edges[cur]。从后向前分析:判定处理ret的值返回值找到环尾ret......
  • 朴素迪氏最短单源路径的原理及C++实现
    Dijkstra算法,翻译为迪杰斯特拉或狄克斯特拉。在下驽钝,记不住如此长的翻译,故简称迪氏。时间复杂度O(n2),端点数的平方。使用前提边的权为正。可以非连通,非连通的距离为-1。原理源点到源点的最短路径只有一个节点{s}。除源点本身外,其它端点的最短路径至少有两个端点,整个路径{s...x2}可......
  • 有向图访问计数的原理及C++实现
    题目现有一个有向图,其中包含n个节点,节点编号从0到n-1。此外,该图还包含了n条有向边。给你一个下标从0开始的数组edges,其中edges[i]表示存在一条从节点i到节点edges[i]的边。想象在图上发生以下过程:你从节点x开始,通过边访问其他节点,直到你在此过程中再次......
  • Windows git bash 命令行提示主机、用户、路径等默认信息 修改
    全局说明命令提示行,默认显示主机、用户、路径等信息,但是有时候截图,有意无意的就会泄露一些信息,被人看到时,太暴露隐私。这个显示右PS1这个变量来管理的,所以就在~/.bash_profile文件里修改想要的样式就可以一、环境下默认的特殊符号所代表的意义:\u:当前用户的账号名称\w:完......
  • Windows下VC++编译器32位memcpy、memmove函数汇编代码详解
    整理者:赤勇玄心行天道QQ号:280604597微信号:qq280604597QQ群:511046632博客:www.cnblogs.com/gaoyaguo  blog.csdn.net/cyz7758520?type=blog大家有什么不明白的地方,或者想要详细了解的地方可以联系我,我会认真回复的!你可以随意转载,无需注明出处!写文档实属不易,我希望大家能支......
  • 深入实践C++11智能指针
    目录概念一、std::auto_ptr二、std::unique_ptr常用函数自定义智能指针对象持有的资源的释放函数三、std::shared_ptr常用函数四、std::enable_shared_from_this五、std::weak_ptr常用函数智能指针使用注意事项智能指针的简单实现概念C/C++语言最为人所诟病的特性之一就是......
  • C++常见入门题题解
    前言因为本人目前比较菜,所以给出的题解都是按照自己的学习进度来的,所以难度是一个循序渐进的过程,由于本人水平有限,望读者能够指出谬误,共同进步。回文数输出#include<bits/stdc++.h>//万能头usingnamespacestd;intmain(void){vector<int>font;//定义一个整型的向......
  • springboot 打 war 包后的访问路径
    http://laremehpe.eu.org:9090/api/access/time 域名:http://laremehpe.eu.org端口号:9090访问路径:/api/access/time/api是tomcat解压后文件夹名称/access是类上的路径名称(@RequestMapping)/time是方法上的路径名称(@RequestMapping) 这里的9090指的是访问服务器的9090......