次短路算法

标签：return   else   const   min   isp   span   入队   cout   ref   

次短路

(一)

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

数组\(dis1\)存放的是到各点的最短路，\(dis2\)存放的是到各点的次短路

\[dis_2[v]=\begin{cases} dis_2[u]+w \dis_1[u]+w \ \ \ \ \ \ \ \ \ dis_1[u]+wdis_1[u]+w \end{cases}\]

(二)换边法

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

Roadblocks

Spfa

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

#include
#include
#include
#include
#include
#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)
{
    queuequ;
    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]

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

#include
#include
#include
#include
#include
#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,vector >,greater > >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

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

#include
#include
#include
#include
#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,vector >,greater > >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]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

次短路算法

标签：return   else   const   min   isp   span   入队   cout   ref   

原文地址：https://www.cnblogs.com/lcbwwy/p/13125183.html