本文共 2523 字，大约阅读时间需要 8 分钟。

之前用Dijkstra算法求过最短路径，求次短路径在之前的方法上做一下修改就可以。

求从s到t的次短路径有两种情况：1、起点s到某个顶点u的最短路+d(u,t)。2、起点到某个顶点u的次短路+d(u,t)。

所以更新路径的时候需要把最短路径和次短路径两个都记录下来。

具体见代码：

#define N 100000+10  #define INF 100000000  typedef pair
   
    P;  int n,r;  struct Edge{ int to, cost; };  vector
    
     G[N];  int dist[N], dist2[N];  void addedge(int u, int v,int w)  {      G[u].push_back(Edge{ v, w });      G[v].push_back(Edge{ u, w });  }  void solve()  {      priority_queue
     
      , greater
      
 >q;      fill(dist, dist + n, INF);      fill(dist2, dist2 + n, INF);      dist[0] = 0;      q.push(P(0, 0));      while (!q.empty())      {          P u = q.top(); q.pop();          int v = u.second, d = u.first;          if (dist2[v] < d)continue;//取出的不是最短路径，也不是次短距离，抛弃          for (int i = 0; i < G[v].size(); i++)          {              Edge&e = G[v][i];              int d2 = d + e.cost;              if (dist[e.to]>d2)//更新最短距离              {                  swap(dist[e.to], d2);                  q.push(P(dist[e.to], e.to));              }              if (dist2[e.to]>d2&&dist[e.to] < d2)//更新次短距离              {                  dist2[e.to] = d2;                  q.push(P(dist2[e.to], e.to));              }          }      }      printf("%d\n", dist2[n - 1]);  }
     
    
   

习题：POJ3225

题意：就是求两个点之间的次短路径（如果最短路径有好多条，那么次短路径是比这些最短路径都长，但比其他路径都短的那条）

代码：

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;#define N 5005#define INF 111111111struct Edge{ int to ,w; bool operator <(const Edge &a)const{ return w > a.w; }};priority_queue
         
           Q;vector
          
            V[N];int n, m;int dis[N], dis2[N];void init(){ for(int i = 1; i <= n; i++){ V[i].clear(); dis[i] = INF; dis2[i] = INF; }}int dijkstra(){ dis[1] = 0; Edge p, q, r; p.to = 1, p.w = 0; Q.push(p); while(!Q.empty()){ p = Q.top(); Q.pop(); int u = p.to; if(p.w > dis2[u])continue; for(int i = 0; i < V[u].size(); i++){ q = V[u][i]; int to = q.to, d = q.w + p.w; if(dis[to] > d){ swap(dis[to], d); r.to = to, r.w = dis[to]; Q.push(r); } if(dis[to] < d && dis2[to] > d){ dis2[to] = d; r.to = to, r.w = d; Q.push(r); } } } return dis2[n];}int main(){ int a, b, w; Edge p; while(cin>>n>>m){ init(); for(int i = 0; i < m; i++){ scanf("%d%d%d", &a, &b, &w); p.to = b; p.w = w; V[a].push_back(p); p.to = a; V[b].push_back(p); } int len = dijkstra(); cout<
           
            <
           
          
         
        
       
      
     
    
   

4 61 2 11 2 51 3 22 3 22 4 12 4 6ans:4

（存在重复走的路径）

转载地址：https://blog.csdn.net/zhj_fly/article/details/75506896 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！