路由选择

admin

在网络通信中，经常需要求最短路径。但完全用最短路径传输有这样一个问题：如果最终在两个终端节点之间给出的最短路径只有一条。则在该路径中的任一个节点或链路出现故障时，信号传输将面临中断的危险。因此，对网络路由选择作了以下改进：
为任意两节点之间通信提供三条路径供其选择，即最短路径、第二最短路径和第三最短路径。
第一最短路径定义为：给定一个不含负回路的网络D={V，A，W}，其中V={v1，v2，…，vn}，A 为边的集合，W 为权的集合，设P1 是D 中最短（v1，vn）路。称P1 为D 中最短（v1，vn）路径，如果D 中有一条（v1，vn）路，P2 满足以下条件：
（1）P2≠P1；
（2）D 中不存在异于P1 的路P，使得W（P1）≤W（P）<W（P2）
则称P2 为D 的第二最短路径。
第三最短路径的定义为：设P2 是D 中第二最短（v1，vn）路径，如果D 中有一条（v1，vn）路P3 满足以下条件：
（1）P3≠P2 并且P3≠P1；
（2）D 中不存在异于P1，P2 的路P，使得W（P2）≤W（P）<W（P3）
则称P3 为D 中第三最短路径。
现给定一有n 个节点的网络，n<=30，求给定两点间的第一、第二和第三最短路径。
【输入】
输入文件route.in 格式如下：
n S T Max （每格数值之间用空格分隔）
M11 M12 … M1n
M21 M22 … M2n
… …
Mn1 Mn2 … Mnn
其中n 为节点数，S 为起点，T 为终点，Max 为一代表无穷大的整数，Mij 描述I 到J 的距离，若Mij=Max，则表示从I 到J 无直接通路，Mii=0。
【输出】
输出文件route.out 包含三条路径的长度（从小到大）。占一行，中间用一个空格分隔
【样例输入】
5 1 5 10000
0 1 3 10000 7
10000 0 1 10000 10000
10000 10000 0 1 4
10000 10000 10000 0 1
10000 1 10000 10000 0
【样例输出】
4 5 6

WWX

带注释的代码
# include<iostream>
# include<cstdio>
# include<cmath>
# include<algorithm>
# include<cstring>
# include<queue>
using namespace std;
const int mn = 35;
const int inf = 0xfffffff;
struct edge{int to,dis,next;};
edge e1[mn*mn],e2[mn*mn];//e1存正向边，e2存反向边
int head1[mn],head2[mn],edge_max;
void add(int x,int y,int z)//加边
{
    ++edge_max;
    e1[edge_max].to=y;
    e1[edge_max].next=head1[x];
    e1[edge_max].dis=z;
    head1[x]=edge_max;
    e2[edge_max].to=x;
    e2[edge_max].dis=z;
    e2[edge_max].next=head2[y];
    head2[y]=edge_max;
}
struct node{
    int id,f,g;//id为节点编号，g为估计函数
    node(int id=0,int f=0,int g=0):id(id),f(f),g(g){}
    bool operator <(const node &a)const{
        if(f==a.f) return g>a.g;
        return f>a.f;
    }
};
int dis[mn];
bool vis[mn];
int n,st,en,maxn,k;
void spfa(int x)//预处理终点到各个节点到的最短路
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[x]=0;
    vis[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head2[u];i;i=e2[i].next)
        {
            if(dis[e2[i].to]>dis[u]+e2[i].dis)
            {
                dis[e2[i].to]=dis[u]+e2[i].dis;
                if(!vis[e2[i].to])
                {
                    vis[e2[i].to]=1;
                    q.push(e2[i].to);
                }
            }
        }
    }
}
void A_star(int x,int y){//第k短路模板
    priority_queue<node>q;
    q.push(node(x,0,0));
    int cnt=0;
    while(!q.empty()){
        node h=q.top();q.pop();
        if(h.id==y){
            if(++cnt==k){//如果是第k次找到这个点，那么第k短路就是h.f
                printf("%d ",h.f);
                return ;
            }
        }
        for(int i=head1[h.id];i;i=e1[i].next){
            q.push(node(e1[i].to,h.g+e1[i].dis+dis[e1[i].to],h.g+e1[i].dis));
        }
    }
}
int main()
{
   int x;
   freopen("route.in","r",stdin);
   freopen("route.out","w",stdout);
   scanf("%d%d%d%d",&n,&st,&en,&maxn);
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
   {
      scanf("%d",&x);
      if(x==maxn || i==j)
        continue;
      add(i,j,x);//加边
   }
   spfa(en);//预处理,不要忘了。（血的教训）
   for(k=1;k<=3;k++)
       A_star(st,en);
   return 0;
}

WWX

第k短路模板
# include<iostream>
# include<cstdio>
# include<cmath>
# include<algorithm>
# include<cstring>
# include<queue>
using namespace std;
const int mn = 35;
const int inf = 0xfffffff;
struct edge{int to,dis,next;};
edge e1[mn*mn],e2[mn*mn];
int head1[mn],head2[mn],edge_max;
void add(int x,int y,int z)
{
    ++edge_max;
    e1[edge_max].to=y;
    e1[edge_max].next=head1[x];
    e1[edge_max].dis=z;
    head1[x]=edge_max;
    e2[edge_max].to=x;
    e2[edge_max].dis=z;
    e2[edge_max].next=head2[y];
    head2[y]=edge_max;
}
struct node{
    int id,f,g;
    node(int id=0,int f=0,int g=0):id(id),f(f),g(g){}
    bool operator <(const node &a)const{
        if(f==a.f) return g>a.g;
        return f>a.f;
    }
};
int dis[mn];
bool vis[mn];
int n,st,en,maxn,k;
void spfa(int x)
{
    queue<int> q;
    for(int i=1;i<=n;i++)
        dis[i]=inf;
    dis[x]=0;
    vis[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head2[u];i;i=e2[i].next)
        {
            if(dis[e2[i].to]>dis[u]+e2[i].dis)
            {
                dis[e2[i].to]=dis[u]+e2[i].dis;
                if(!vis[e2[i].to])
                {
                    vis[e2[i].to]=1;
                    q.push(e2[i].to);
                }
            }
        }
    }
}
void A_star(int x,int y){
    if(x==y) k++;
    priority_queue<node>q;
    q.push(node(x,0,0));
    int cnt=0;
    while(!q.empty()){
        node h=q.top();q.pop();
        if(h.id==y){
            if(++cnt==k){
                printf("%d ",h.f);
                return ;
            }
        }
        for(int i=head1[h.id];i;i=e1[i].next){
            q.push(node(e1[i].to,h.g+e1[i].dis+dis[e1[i].to],h.g+e1[i].dis));
        }
    }
}
int main()
{
   int x;
   freopen("route.in","r",stdin);
   freopen("route.out","w",stdout);
   scanf("%d%d%d%d",&n,&st,&en,&maxn);
   for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
   {
      scanf("%d",&x);
      if(x==maxn || i==j)
        continue;
      add(i,j,x);
   }
   spfa(en);
   for(k=1;k<=3;k++)
       A_star(st,en);
   return 0;
}

WWX

这到题可以用求第k短路的方法去做
虽然有点小题大作，不过复杂度应该比其它解法要低

admin

忘记在哪里看到这个题的了，次短路径经典题目。

首先求出第一短路径；
枚举删除第一短路径上一条边，再求此时的最短路径；总这些较优路径中选一条最短的，即为第2短路径；
求第3短路径方法类似，枚举从第一短路径上删除一条边，第2短路径上删除一条边，再求最短路经；从这些路径中选出最短的即为第3短。
时间复杂度为O(n^4)。