【初赛】最短路 次短路 k短路 - Slayer

最短路、次短路、k短路算法总结与C++代码示例

一、最短路算法

1. Dijkstra算法（单源最短路，非负权图）

• 适用场景：有向/无向图，边权非负，求单源最短路径
• 时间复杂度：O(m log n)（ n 为顶点数，m 为边数，使用优先队列+邻接表）

2. Bellman-Ford 算法（单源最短路，支持负权图）

• 适用场景：有向图，可处理负权边，能检测负环
• 时间复杂度：O (nm)

spfa

struct Edge {int u, v, w;
};vector<Edge> edge;int dis[MAXN], u, v, w;
constexpr int INF = 0x3f3f3f3f;bool bellmanford(int n, int s) {memset(dis, 0x3f, (n + 1) * sizeof(int));dis[s] = 0;bool flag = false;  // 判断一轮循环过程中是否发生松弛操作for (int i = 1; i <= n; i++) {flag = false;for (int j = 0; j < edge.size(); j++) {u = edge[j].u, v = edge[j].v, w = edge[j].w;if (dis[u] == INF) continue;// 无穷大与常数加减仍然为无穷大// 因此最短路长度为 INF 的点引出的边不可能发生松弛操作if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;flag = true;}}// 没有可以松弛的边时就停止算法if (!flag) {break;}}// 第 n 轮循环仍然可以松弛时说明 s 点可以抵达一个负环return flag;
}

二、次短路

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

• 方法一:用 dijkstra 算法 从起点开始 同时维护【最短路数组(dis1[])】和【次短路 数组(dis2[])】

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

  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <string>
  #include <cmath>
  #include <iostream>
  #include <algorithm>
  #include <queue>
  #include <map>
  #include <stack>
  #include <vector>
  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 <node> G[Maxn];
  void Dijkstra(){priority_queue <node> 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 <= M ; i++){int u , v , w;	scanf(" %d %d %d",&u,&v,&w);G[u].push_back((node){v,w});G[v].push_back((node){u,w});}Dijkstra();printf("%d\n",dis2[N]);}
  }

• 方法二:还是用到dikstra 算法 分别用两个 dis1[]数组 和 dis2[]数组 分别 维护 从起点 和 从终点开始 的 最短路 --然后枚举 所有边 ， 将边的两个端点 连上 起点和终点 看是不是等于最短路，相等则跳过 ， 不相等 则 更新 和 次短路(inf)取min

  #include <cstdio>
  #include <cstdlib>
  #include <cstring>
  #include <string>
  #include <cmath>
  #include <iostream>
  #include <algorithm>
  #include <queue>
  #include <map>
  #include <stack>
  #include <vector>
  using namespace std;
  typedef long long LL;
  const int Maxn = 1e5 + 7;
  const int Inf = 1e9 + 7;
  int N , M , cnt , ans;
  int start = 1 , End = N;
  int dis1[Maxn] , dis2[Maxn];
  bool vis[Maxn];
  struct node{int v , w;friend bool operator < (node a , node b){return a.w > b.w;}
  };
  struct edge{int x , y , w;
  }A[Maxn << 1];
  vector <node> G[Maxn];void GetDis(int op){priority_queue <node> que;if(!op)	que.push((node){start , 0});else	que.push((node){End , 0});int v , w;node q;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 < G[v].size() ; i++){to_v = G[v][i].v , to_w = G[v][i].w + w;if(!op && dis1[to_v] > 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 <= cnt ; i++){x = A[i].x , y = A[i].y , w = A[i].w;int temp = dis1[x] + dis2[y] + w;if(temp == flag)	continue;else ans = min(ans , temp);}
  }int main()
  {while(~scanf(" %d %d",&N,&M)){cnt = 0;for(int i = 1 ; i <= M ; i++){int u , v , w;	scanf(" %d %d %d",&u,&v,&w);G[u].push_back((node){v,w});G[v].push_back((node){u,w});A[++cnt].x = u , A[cnt].y = v , A[cnt].w = w;A[++cnt].x = v , A[cnt].y = u , A[cnt].w = w;}Dijkstra();FindCdl();printf("%d\n",ans);}
  }
  

三、第K短路：

第K短路 其实 就是BFS + A（A启发式搜索优化剪枝）

首先求 从 终点 到 每个点的最短路 用 dis[ ] 数组存储

然后使用 A* 函数 ， F[x] = H[x] + G[x]

题目：POJ 2449

具体讲解在代码内

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
using namespace std;
typedef long long LL;
const int Maxn = 1e5 + 7;
const int Inf = 1e9 + 7;
int N , M , K;
int start , End;
int ans;//最短路部分
int dis[Maxn];
bool vis[Maxn];
struct node{int v , w;friend bool operator < (node a , node b){return a.w > b.w;}
};/** A* 启发式搜索函数 F[x] = H[x] + G[x]* 变量 Hx 表示搜索到当前点 所用的代价* 变量 Gx 是估价函数 （估价函数要小于等于实际值，否则出错）*/
struct edge{int v , Hx , Gx;friend bool operator < (edge a , edge b){return a.Hx + a.Gx > b.Hx + b.Gx;}
};
/** count 记录第几次BFS拓展到此点* 当 count == K 时  不再对此点继续进行拓展（因为拓展的点必定大于 第K短路）*/
int Count[Maxn];vector <node> G[Maxn] , G2[Maxn];/** （因为是有向图所以反向建图）* 求End到每个点的最短路*/
void Dijkstra(){fill(vis , vis+N+1 , false);fill(dis , dis+N+1 , Inf);priority_queue <node> 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 <edge> 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 <= N ; i++)	G[i].clear();for(int i = 1 ; i <= M ; i++){int u , v , w;	scanf(" %d %d %d",&u,&v,&w);G[u].push_back((node){v, w});G2[v].push_back((node){u, w});}scanf(" %d %d %d",&start , &End , &K);//此题要求start和End相同的时候 第一短路不是0 ，所以K++if(start == End)	K++;Dijkstra();Astar();printf("%d\n",ans);}return 0;
}

后面两个来自