最短路算法

多源最短路

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

• 大概是这么个流程
• 

• //结构体Node用来记录点的位置与当前最短路struct Node{	int dis,pos;	friend bool operator < (Node A,Node B){		return A.dis > B.dis;	}};//优先队列，每次取当前路径最短的点priority_queue<Node>q;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

经典咏流传​

• SPFA一般用于Dijkstra不适用的地方，比如负权图、判断负环等

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