最短路算法

多源最短路

Floyd

• 适用范围：无负权回路即可，边权可正可负，运行一次算法即可求得任意两点间最短路。

• 用$f(i,j,k)$表示只考虑前$k$个点，$i$到$j$的最短路

  枚举$k$作为中转点

  从$i$点到$j$点，可以直接到达，也可以选择通过$k$点中转后到达

  如果通过$k$点中转后，从$i$到$j$的距离缩短，那么就将$f(i,j,k)$更新为$f(i,k,k-1)+f(k,j,k-1)$

  所以状态转移方程为，$f(i,j,k)=\min(f(i,j,k-1),f(i,k,k-1)+f(k,j,k-1))$

  又由于$k$仅与$k-1$有关，所以可以用滚动数组优化掉这一维

  进行滚动数组优化后，可得代码

  for(int k = 1;k<=n;k++){
      for(int i = 1;i<=n;i++){
          for(int j = i;j<=n;j++){
              f[i][j] = min(f[i][j],f[i][k]+f[k][j]);
          }
      }
  }

单源最短路

Dijkstra

• 大概是这么个流程

• 

• ```cpp
  //结构体Node用来记录点的位置与当前最短路
  struct Node{

  int dis,pos;
  friend bool operator < (Node A,Node B){
      return A.dis > B.dis;
  }
  

  };
  //优先队列，每次取当前路径最短的点
  priority_queueq;
  void Dijkstra(){

  //每个点到自己的路径长度为0
  //s为源点
  dis[s] = 0;
  //源点到源点的最短路为0
  q.push((Node){0,s});
  
  while(!q.empty()){
      //弹出元素为到源点路径最短的点
      Node tmp = q.top();
      q.pop();
      int x = tmp.pos;
      int d = tmp.dis;
      //如果这个点曾经访问过则跳过
      if(vis[x]) continue;
      //标记这个点访问过
      vis[x] = 1;
      //链式向前星存图
      for(int i = head[x];i;i = edge[i].nxt){
          //枚举当前点可以到达的点y_
          int y_ = edge[i].to;
          //如果从源点到y_的距离长于从源点先到x再从x到y_的距离
          //即从源点到y_的距离可以通过x点缩短时，更新最短路
          if(dis[y_] > dis[x] + edge[i].dis){
              dis[y_] = dis[x] + edge[i].dis;
              //如果y_这个点没有到达过，将其压入队列
              //现在可以通过y_中转到目标点了
              if(!vis[y_]) q.push((Node){dis[y_],y_});
          } 
      }
  }
  

  }

  #### SPFA
  
  ![](https://raw.githubusercontents.com/gongxi-cn-ln-dl/tuchuang/main/PicGo/202202112146325.jpg)
  
  ~~经典咏流传~~
  
  - SPFA一般用于Dijkstra不适用的地方，比如负权图、判断负环等
  
  - ```cpp
    queue<int> q;
    int dis[N];
    int vis[N];
    int ans = 0;
    void SPFA(int s){
    	vis[s] = 1;
    	q.push(s);
    	while(!q.empty()){
    		int t = q.front();
    		q.pop();
    		vis[t] = 0;
    		for(int i = head[t];i;i=edge[i].nxt){
    			int to_ = edge[i].to;
    			int dis_ = edge[i].w;
    			if(dis[to_]>dis[t]+dis_){
    				dis[to_] = dis[t]+dis_;
    				if(!vis[to_]){
    					q.push(to_);
    					vis[to_] = 1;
    				} 
    			}
    		}
    	}
        return;
    }