次短路（两种方式） && 第K短路

2024-05-29 12:31| 来源: 网络整理| 查看: 265

次短路算法：

有两种比较简单实现次短路的思想

方法一：用 dijkstra 算法从起点开始同时维护【最短路数组（dis1[ ]）】和【次短路数组（dis2[ ]）】方法二：还是用到dijkstra 算法分别用两个 dis1[ ] 数组和 dis2[ ] 数组分别维护从起点和从终点开始的最短路 ——然后枚举所有边，将边的两个端点连上起点和终点看是不是等于最短路，相等则跳过，不相等则更新和次短路（Inf）取min

题目：POJ - 3255

方式一：

tips：其中if（dis2[v] < w） continue; 这句为true的时候，说明当前节点v 的次短路已经被更新过了，如果w比次短路大，说明它肯定是 >= 第三短路，也就不用更新了。

#include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; const int Maxn = 1e5 + 7; const int Inf = 1e9 + 7; int N , M; int dis1[Maxn] , dis2[Maxn]; struct node{ int v , w; friend bool operator < (node a , node b){ return a.w > b.w; } }; vector G[Maxn]; void Dijkstra(){ priority_queue que; fill(dis1 , dis1+N+1 , Inf); fill(dis2 , dis2+N+1 , Inf); int start = 1; dis1[start] = 0; que.push((node){start , 0}); node q; int v , w; while(!que.empty()){ q = que.top(); que.pop(); v = q.v , w = q.w; if(dis2[v] < w) continue; int to_v , to_w; for(int i = 0 ; i < G[v].size() ; i++){ to_v = G[v][i].v , to_w = G[v][i].w + w; if(dis1[to_v] > to_w){ que.push((node){to_v , to_w}); swap(dis1[to_v] , to_w); } if(dis2[to_v] > to_w && dis1[to_w] < to_w){ dis2[to_v] = to_w; que.push((node){to_v , to_w}); } } } } int main() { while(~scanf(" %d %d",&N,&M)){ for(int i = 1 ; i b.w; } }; struct edge{ int x , y , w; }A[Maxn to_w){ dis1[to_v] = to_w; que.push((node){to_v , to_w}); } else if(op && dis2[to_v] > to_w){ dis2[to_v] = to_w; que.push((node){to_v , to_w}); } } } } void Dijkstra(){ fill(dis1 , dis1+N+1 , Inf); fill(dis2 , dis2+N+1 , Inf); start = 1 , End = N; dis1[start] = dis2[End] = 0; fill(vis , vis+N+1 , false); GetDis(0); fill(vis , vis+N+1 , false); GetDis(1); } void FindCdl(){ int flag = dis1[End]; int x , y , w; ans = Inf; for(int i = 1 ; i b.Hx + b.Gx; } }; /* * count 记录第几次BFS拓展到此点 * 当 count == K 时不再对此点继续进行拓展（因为拓展的点必定大于第K短路） */ int Count[Maxn]; vector G[Maxn] , G2[Maxn]; /* * （因为是有向图所以反向建图） * 求End到每个点的最短路 */ void Dijkstra(){ fill(vis , vis+N+1 , false); fill(dis , dis+N+1 , Inf); priority_queue que; que.push((node){End , 0}); dis[End] = 0; node q; int v , w; while(!que.empty()){ q = que.top(); que.pop(); v = q.v , w = q.w; if(vis[v]) continue; vis[v] = true; int to_v , to_w; for(int i = 0 ; i < G2[v].size() ; i++){ to_v = G2[v][i].v , to_w = G2[v][i].w + w; if(dis[to_v] > to_w){ dis[to_v] = to_w; que.push((node){to_v , to_w}); } } } } /* * 第K短路算法 = A* + BFS */ void Astar(){ ans = -1; fill(Count , Count+N+1 , 0); priority_queue que; que.push((edge){start , 0 , 0}); edge q; int v , Hx , Gx; while(!que.empty()){ q = que.top(); que.pop(); v = q.v , Hx = q.Hx , Gx = q.Gx; Count[v]++; if(Count[v] == K && v == End){ ans = Hx + Gx; break; } if(Count[v] > K) continue; int to_v , to_hx , to_gx; for(int i = 0 ; i < G[v].size() ; i++){ to_v = G[v][i].v; to_hx = Hx + G[v][i].w; to_gx = dis[to_v]; que.push((edge){to_v , to_hx , to_gx}); } } while(!que.empty()) que.pop(); return; } int main() { while(~scanf(" %d %d",&N,&M)){ for(int i = 1 ; i

【本文地址】

公司简介

联系我们