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

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;
};

#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]);
            }
        }
    }
}