Floyd&Dijkstra

拓展，多条路径Floyd算法

Floyd算法是一种求解“多源最短路”问题的算法

在Floyd算法中，图一般用邻接矩阵存储，边权可正可负（但不允许负环），利用动态规划的思想，逐步求解出任意两点之间的最短距离

我们需要准备的东西很少，只需要一个d数组：int[N][N][N]，初始为无穷大，无穷大表示两点之间没有路径

d[k][i][j]表示路径（除去起点和终点）中编号最大的点编号≤k的情况下，点i到点j的最短距离

但是实际上k这一维度是可以优化掉的，所以直接用int d[N][N]

d[i][j]表示考虑到当前情况下，点i到点j的最短距离

这里3是中转点

//注意k作为中转点，必须放外层
for(int k=1;k<=n;k++)
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);

通过这段代码我们不难看出，Floyd算法的时间复杂度为O(n^3)，是比较高的，所有一般只能处理n≤500的图论问题

这也是一个提示，当遇到n≤500的图论问题时，可以考虑Floyd算法

Dijkstra算法

Dijkstra算法是一种高效的处理非负边权的“单源最短路”问题的算法，例如求出所有点距离源点1的距离，可以说Dijkstra是最重要的图论算法之一

Dijkstra算法利用了贪心和动态规划的思想，也有多个版本：朴素版、堆优化版

这里直接讲解Dijkstra算法的堆优化版本（priority_queue优先队列实现，最常用、最高效），朴素版相比堆优化版没有任何优势

堆优化版本的时间复杂度为O(nlogn)

Dijkstra算法中，图采用邻接表的方式存储，比较适合稀疏图

算法需要准备的东西：

int d[N];

d[i]表示点i距离源点的最短距离

bitsetvis表示某个点是否走过（也可以用bool类型），按照Dijkstra的贪心思想，第一次走到的时候得到的距离一定是最短距离，所以一个点不可能走第二次

struct Node
{
  int x,w;//x表示点编号，w表示源点到x的最短距离
  bool operater<(const Node &u) const//重载比较函数
  {
    return w==u.w?x<u.x:w>u.w;//按照w降序，在优先队列中w最小的作为堆顶
  }
}

priority_queue<Node> pq;

void dijkstra(int st)//st为起点
{
  pq.push({st,d[st]=0});
  while(pq.size())//只要队列不为空
  {
    auto[x,w]=pq.top();pq.pop();//取出对头元素
    if(vis[x]) continue;//如果走过直接跳过
    vis[x]=true;//标记为走过
    for(const auto &[y,dw]:g[x])//x->y，边权为dw的边
    {
      if(d[x]+dw<d[y])//这一步十分关键
      {
        d[y]=d[x]+dw;
        pq.push({y,d[y]});//继续往外拓展
      }
    }
  }
}

 拓展，多条路径