南京机关建设网站,珠海网站哪家好,洛阳设计网站公司,南宁两学一做网站SPFA (Bellman-Ford 的队列优化版本)#xff1a;
1、求单源最短路径#xff0c;即每个点到源点的最短距离
2、可以处理负权边的情况
3、可以判断是否出现负权回路
#includeiostream
#includevector
#includecstring
#includequeue
using…SPFA (Bellman-Ford 的队列优化版本)
1、求单源最短路径即每个点到源点的最短距离
2、可以处理负权边的情况
3、可以判断是否出现负权回路
#includeiostream
#includevector
#includecstring
#includequeue
using namespace std;
struct node{int x,y,t;
};
int n,m,dis[10001],count[10001];
vectornode g[10001];
bool flag,inque[10001];
queueint q;
bool spfa(int S){memset(dis,0x7f,sizeof(dis));memset(inque,false,sizeof(inque));dis[S]0;count[S];inque[S]true;q.push(S);while(!q.empty()){int uq.front();q.pop();inque[u]false;for(int i0;ig[u].size();i){int vg[u][i].y;int wg[u][i].t;if(dis[u]wdis[v]){dis[v]dis[u]w;if(inque[v]false){q.push(v);count[v];inque[v]true;if(count[v]n){return false;}}}}}return true;
}
int main(){cinnm;for(int i1;im;i){int x,y,v;cinxyv;g[x].push_back((node){x,y,v});}flagspfa(1);if(flagtrue){coutdis[n];}return 0;
}时间复杂度O(kM)~O(NM)
常见技巧 在给平面直角坐标系构图判断连通性时仅需要将相邻的点连接先按照x坐标或y坐标排序 求一点到多点的距离可以反向连边 有时会进行拆点
Floyed:
1、求多源最短路径即点与点之间的最短距离
2、可以处理负权边的情况
3、不能出现负环
一个应用最短回路无向图有向图算d[s][s]
#includeiostream
using namespace std;
int dist[101][101],cost[101][101],n,m,s,t,w,ans;
const int maxn99999999;
int main(){while(cinnm){ansmaxn;for(int i1;in;i){for(int j1;jn;j){dist[i][j]maxn;cost[i][j]-1;}}for(int i1;im;i){cinstw;dist[s][t]dist[t][s]w;cost[s][t]cost[t][s]w;}for(int k1;kn;k){for(int i1;ik;i){for(int ji1;jk;j){if(cost[i][k]-1||cost[k][j]-1)continue;ansmin(ans,dist[i][j]cost[i][k]cost[k][j]);}}//省略这段循环则为floyed基本模版 for(int i1;in;i){for(int j1;jn;j){dist[i][j]min(dist[i][j],dist[i][k]dist[k][j]);}}}if(ans!maxn)coutansendl;else coutNo solution.endl; }
}时间复杂度O(N^3)
Dijkstra
1、求单源最短路径
2、不能处理负权
普通版
void dijkstra() {memset(dis,127/3,sizeof(dis));//初始化 v[1]1;dis[1]0;for(int i1;in;i){int k0;for(int j1;jn;j) if(!v[j](k0||dis[j]dis[k])) kj;v[k]1;for(int j1;jn;j) if(!v[j]dis[k]a[k][j]dis[j])dis[j]dis[k]a[k][j];}
}时间复杂度O(N^2)
堆优化版
int dis[N],vis[N];
priority_queuepr,vectorpr ,greaterpr que;
void dijkstra(int s){memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]0;que.push(make_pair(0,s));while(!que.empty()){pr tmpque.top();que.pop();int dtmp.first;int utmp.second;//if(d!dis[u]) continue;(等价于if(vis[u]) continue;)if(vis[u]) continue;vis[u]1;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;int wedge[i].w;if(dis[v]dis[u]w){dis[v]dis[u]w;que.push(pr(dis[v],v));}}}
}其它优化博客
时间复杂度O((MN)logM) 其中M为边数N为点数 update:2021/1/23
如何用单源最短路径算法求多源最短路径问题可以出发/终止的点有多个,与Floyed求解问题不同
---- 建立一个超级起点、超级终点将所有可能的起点、终点和超级起点、超级终点连接
