次短路算法

次短路

(一)

• 从(父节点)到(子节点)次短路直接更新(通常在最短路已经确定的情况下才进行直接更新次短路)
• 从(父节点)到(子节点)最短路不更新，但是距离比次短路距离小，更新次短路
• 从(父节点)到(子节点)最短路更新，原来的最短路就成了次短路

数组存放的是到各点的最短路，存放的是到各点的次短路

• 

(二)换边法

• 1到n的次短路长度必然产生于：从走到的最短路 + + 到的最短路(与次小生成树有些相似)
  1.首先预处理好1到每一个节点的最短路，和n到每一个节点的最短路
  2.然后枚举每一条边作为中间边或者，如果加起来长度等于最短路长度则跳过，否则更新。
  从走到的最短路 + + 到的最短路,只比大，比其他的都小的那个值。

Roadblocks

Spfa

• 一直更新记录,找出的是各点的最短路和次短路

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
int dis[5500];
int dis2[5500];
int vis[5500];
int head[200100],cnt;
struct node
{
    int v,w;
    int nxt;
} edge[200100];
void add(int x,int y,int w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
void Dijkstra(int x)
{
    queue<int>qu;
    memset(vis,0,sizeof(vis));
    memset(dis,INF,sizeof(dis));
    memset(dis2,INF,sizeof(dis2));
    dis[x]=0;
    vis[x]=1;
    qu.push(x);
    while(!qu.empty( ))
    {
        int u=qu.front( );
        qu.pop( );
        vis[u]=0;
        for(int i=head[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(dis[v]>dis[u]+w)//最短路更新，原来的最短路变成次短路
            {
                dis2[v]=dis[v];
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    qu.push(v);
                    vis[v]=1;
                }
            }
            if(dis2[v]>dis2[u]+w)//次短路直接更新(通常是最短路确定后才进行）
            {
                dis2[v]=dis2[u]+w;
                if(!vis[v])
                {
                    qu.push(v);
                    vis[v]=1;
                }
            }
            if(dis2[v]>dis[u]+w&&dis[v]<dis[u]+w)//最短路不更新，但距离比次短路小
            {
                dis2[v]=dis[u]+w;
                if(!vis[v])
                {
                    qu.push(v);
                    vis[v]=1;
                }
            }
        }
    }
}
int main( )
{
    int n,r,x,y,w;
    memset(head,-1,sizeof(head));
    cnt=0;
    scanf("%d%d",&n,&r);
    for(int i=1; i<=r; i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    Dijkstra(1);
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis[i]);
    }
    cout<<endl;
    for(int i=1;i<=n;i++)
    {
        printf("%d ",dis2[i]);
    }
    return 0;
}

利用dijkstra求出到各点的最小距离，到各点的距离，然后枚举每条边，找出第二小的值

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int M=200010;
int head[M],cnt;
struct node
{
    int v,w,nxt;
}edge[M];
int dis1[5050];
int disn[5050];
int vis[5050];
void add(int x,int y,int w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
void Dijkstra(int x,int dis[ ])
{
    memset(vis,0,sizeof(vis));
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qu;
    dis[x]=0;
    qu.push(make_pair(0,x));
    while(!qu.empty( ))
    {
        int u=qu.top( ).second;
        qu.pop( );
        if(!vis[u])
        {
            vis[u]=1;
            for(int i=head[u];i!=-1;i=edge[i].nxt)
            {
                int v=edge[i].v;
                if(dis[v]>dis[u]+edge[i].w)
                {
                    dis[v]=dis[u]+edge[i].w;
                    qu.push(make_pair(dis[v],v));
                }
            }
        }
    }
}
int main( )
{
    int n,r;
    scanf("%d%d",&n,&r);
    memset(head,-1,sizeof(head));
    cnt=0;
    int x,y,w;
    for(int i=1;i<=r;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    memset(dis1,INF,sizeof(dis1));
    memset(disn,INF,sizeof(disn));
    Dijkstra(1,dis1);
    Dijkstra(n,disn);
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<dis1[i]<<" ";
    // }
    // cout<<endl;
    // for(int i=1;i<=n;i++)
    // {
    //     cout<<disn[i]<<" ";
    // }
    // cout<<endl;
    int ans=dis1[n];
    int temp=INF;
    for(int i=1;i<=n;i++)
    {
        for(int j=head[i];j!=-1;j=edge[j].nxt)
        {
            int v=edge[j].v;
            int w=dis1[i]+edge[j].w+disn[v];
            if(w==ans)
            {
                continue;
            }
            else
            {
                temp=min(temp,w);
            }
            
        }
    }
    cout<<temp<<endl;
    return 0;
}

一边更新最短路，一边更新次短路

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
using namespace std;
const int M=200000+10;
int head[M],cnt;
struct node
{
    int v,w,nxt;
}edge[M];
int dis1[5005];
int dis2[5005];
void add(int x,int y,int w)
{
    edge[++cnt].nxt=head[x];
    edge[cnt].v=y;
    edge[cnt].w=w;
    head[x]=cnt;
}
void Dijkstra(int x)
{
    memset(dis1,INF,sizeof(dis1));
    memset(dis2,INF,sizeof(dis2));
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >qu;
    dis1[x]=0;//最短路初始值为0，次短路无穷大
    qu.push(make_pair(0,x));
    while(!qu.empty( ))
    {
        int w=qu.top( ).first;//弹出最小值，或许是最短路，或许是次短路
        int u=qu.top( ).second;
        qu.pop( );
        if(dis2[u]<w)//弹出来的值比当前的次短路大，就可以跳过这个
        {
            continue;
        }
        for(int i=head[u];i!=-1;i=edge[i].nxt)
        {
            int v=edge[i].v;
            int cost=w+edge[i].w;//u到v的花费
            if(dis1[v]>cost)//花费大于原来的最小值，更新最短路
            {
                swap(dis1[v],cost);//交换值
                qu.push(make_pair(dis1[v],v));//压入队列
            }
            if(dis2[v]>cost&&cost>dis1[v])//交换次短路
            {
                swap(dis2[v],cost);
                qu.push(make_pair(dis2[v],v));//压入队列，之所以次短路要压入队列是因为后面更新需要。
                                             //例子：dis[2] = 10, dis2[2] = 20 有一条边 2 到 6 的边权值为 5                 
                                            //如果不把 dis2 入队，那么之后的算法中 dis[6] = 15, dis2[6] = INF              
                                           //只有当队列里有 20 这个值，才能 20+5 得出 25，然后更新 dis2[6] = 25 
            }
        }
    }
}
int main( )
{
    int n,r;
    scanf("%d%d",&n,&r);
    memset(head,-1,sizeof(head));
    cnt=0;
    int x,y,w;
    for(int i=1;i<=r;i++)
    {
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    Dijkstra(1);
    printf("%d\n",dis2[n]);
    return 0;
}