题意就是要求第K短的路的长度(S->T)。

最短路径问题包括:

对于K短路,朴素想法是bfs,使用优先队列从源点s进行bfs,当第K次遍历到T的时候,就是K短路的长度。

1、单源最短路。

但是这种方法效率太低,会扩展出很多状态,所以考虑用启发式搜索A*算法。

2、任意两点间的最短路。

估价函数 = 当前值 + 当前位置到终点的距离,即F(p) = G(p) + H(p)。 

3、次短路和k短路。

G(p): 当前从S到p所走的路径距离

4、差分约束系统。

H(p): 当前点p到终点T的最短路径距离  
—可以先将整个图边方向取反然后以T为源点求个最短路,用SPFA提速

5、DAG图上的单源最短路。

F(p): 从S按照当前路径走到p然后走到T一共至少走多远

6、最小环。

所以我们结合SPFA+A*可以解决。

 

注意:当S==T时,需要计算第K+1短路,因为从S->T这条长度为0的路径不能算在内。

一、单源最短路

还有,SPFA处判了一下负环。SPFA算法中,如果某个点出队次数大于n,说明此处存在负环。

算法: Dijkstra 、 Bellman – Ford 、SPFA

代码:

Dijkstra: 除了路径记录和更新距离数组的部分意外,和Prim算法的实现完全一样。使用邻接矩阵建图,时间复杂度为O(n*n)。使用邻接表可能会快一些。堆优化比较麻烦,没学。缺点是图中不能含有负圈。

图片 1图片 2

Bellman – Ford :可以处理负圈。以链式前向星建图,时间复杂度为O (n*m)。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <functional>
#define Mod 1000000007
using namespace std;
#define N 1007

struct node
{
    int v;
    int g,f; //f = g+h
    bool operator < (const node &a)const
    {
        if(a.f == f)
            return a.g < g;
        return a.f < f;
    }
};

struct Edge
{
    int v,w,next;
}G[100*N],G2[100*N];

int head[100*N],head2[100*N];
int vis[N],dis[N];
int out[N];
int n,m,K,S,T,tot,tot2;

void addedge(Edge *G,int& tot,int *head,int u,int v,int w)
{
    G[tot].v = v;
    G[tot].w = w;
    G[tot].next = head[u];
    head[u] = tot++;
}

int SPFA(int s,int head[N],Edge G[N],int dis[N])
{
    int i;
    queue<int> que;
    for(i=0;i<=n;i++)
        dis[i] = Mod;
    memset(vis,0,sizeof(vis));
    memset(out,0,sizeof(out));
    que.push(s);
    vis[s] = 1;
    dis[s] = 0;
    while(!que.empty())
    {
        int now = que.front();
        que.pop();
        vis[now] = 0;
        out[now]++;
        if(out[now] > n)
            return 0;
        for(int k=head[now];k!=-1;k=G[k].next)
        {
            if(dis[G[k].v] > dis[now] + G[k].w)
            {
                dis[G[k].v] = dis[now] + G[k].w;
                if(!vis[G[k].v])
                {
                    vis[G[k].v] = 1;
                    que.push(G[k].v);
                }
            }
        }
    }
    return 1;
}

int A_Star(int head[N],Edge G[N],int dis[N])
{
    node tmp,now;
    int cnt = 0;
    priority_queue<node> que;
    if(S == T)
        K++;
    if(dis[S] == Mod)
        return -1;
    tmp.v = S;
    tmp.g = 0;
    tmp.f = tmp.g+dis[S];
    que.push(tmp);
    while(!que.empty())
    {
        tmp = que.top();
        que.pop();
        if(tmp.v == T)
            cnt++;
        if(cnt == K)
            return tmp.g;
        for(int i=head[tmp.v];i!=-1;i=G[i].next)
        {
            now.v = G[i].v;
            now.g = tmp.g + G[i].w;
            now.f = now.g + dis[now.v];
            que.push(now);
        }
    }
    return -1;
}

int main()
{
    int i,j,u,v,w;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(head,-1,sizeof(head));
        memset(head2,-1,sizeof(head2));
        tot = tot2 = 1;
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&w);
            addedge(G,tot,head,u,v,w);   //原图
            addedge(G2,tot2,head2,v,u,w);   //反图
        }
        scanf("%d%d%d",&S,&T,&K);
        if(SPFA(T,head2,G2,dis))
        {
            int k_len = A_Star(head,G,dis);
            printf("%d\n",k_len);
        }
        else
            puts("-1");
    }
    return 0;
}

SPFA: 优化的Bellman – Ford算法,可以处理负圈。期望的时间复杂度为O(k*m),k<=2。普遍认为其效率高于朴素的Dijkstra,低于堆优化的Dijkstra。

View Code

题目:

 

多源转单源  hdu2066一个人的旅行(是谁说新手刷杭电11页的,学了最短路还卡了很久)

来回最短路(有向图) 建反向图  hdu1535Invitation Cards 

有限制的最短路   hdu3873 Invade the Mars  
http://www.cnblogs.com/Potato-lover/p/3955179.html

二分法求带限制的最短路  hdu2962 Trucking  
(二分查找的应用实在太广了,二分匹配、网络流都有二分技术)

(综合题)强连通+最短路 poj3114  

 

二、任意两点间的最短路

解决的问题:给出一幅图(有向或者无向),有多次询问,问任意两点之间的最短距离是多少。

暴力的方法:运行多次最短路算法。一般这种题目的数据量大,此算法复杂度太高,不适用。

Floyd算法:邻接矩阵建图,三重循环,时间复杂度为O(n*n*n)。

提醒:初学者一般会把算法混淆。比如说,把这种题目理解为LCA问题,然后用离线的Tarjan算法来做,时间复杂度是O(m+q),不是更快么?需要知道的是**LCA问题是指树的最近公共祖先,其解题范围是树。对于有环的图是无能为力的。**

题目:

输出最短路的路径(字典序最小) 
hdu1385Minimum Transport Cos 
  传送门:http://www.cnblogs.com/Potato-lover/p/3959795.html

 

三、次短路和k短路

字面上看次短就是第二路边,归结到K短路就可以了。实现却不能这样做,原因是算法的实现不能这样做。说到底还是时间复杂度的问题。

次短路是通过修改Dijkstra算法而实现的。时间复杂度是O(n*n)。

K短路是通过SPFA+A*实现的。如果只求K短路的值效率挺高的,但是如果要求与K短路值相同的路径有多少条,这个就很复杂了。

暴力的方法:求一遍最短路,记录路径并记录任意两点之间的路径之间的最大边,枚举所有边。(类似与Prim暴力求次小生成树)。

下面是K短路的实现:

SPFA + A* 实现K短路

K短路要用到A*算法,A*算法通过一个估价函数f(h)来估计途中的当前点p到终点的距离,并由此决定它的搜索方向,当这条路径失败时,它会尝试其他路径。对于A*,估价函数 = 当前值 + 当前位置到终点的距离, 即f (p) = g (p) + h (p) ,每次扩展估计函数值最小的一个。对于K短路算法来说,g (p) 为当前从s到p所走的路径的长度,h (p)为从点p到t的最短路的长度,则f (p)的意义就是从s按照当前路径走到p后再走到终点t一共至少要走多远。

具体实现步骤:

使用链式前向星来存储图, 由于需要预处理所有的点到终点T的最短路径,就需要将图G中所有的边反响得到G1再从终点T做单源最短路径,所以实际上是两张图。

1、将有向图的所有边反向。以T(终点)为源点,求解T到所有点的最短距离。这一步可以用Dijkstra 或者 SPFA算法。我用的是 SPFA(shortest  path  faster  algorithm)。

2、新建一个优先队列,将源点S加入到队列中。

3、从优先队列中弹出f (p)最小的p,如果点p就是t ,则计算t出队的次数,如果当前为T的第K次出队,则当前路径的长度就是s到t的第K短路的长度,算法结束。否则,遍历与p项链的所有的边,将扩展出的到p的邻接点信息加入到优先队列。

注意:当s = =t时需要计算K+1短路,以为s到t这条距离为0的路不能算在这K短路中,这时只需将K加1后再求第K短路即可。

题目:

次短路 hdu3191  hdu1688 

K短路 poj2499

 国界传送门:http://www.cnblogs.com/wally/archive/2013/04/16/3024490.html

 

四、差分约束系统

 我已经做出总结。
传送门:http://www.cnblogs.com/Potato-lover/p/3959979.html

 

五、DAG图上的单源最短路

伪代码:

1、初始化,入度为0的结点dist为0,其他的结点的dist为INF。

2、对DAG进行拓扑排序,得到拓扑序列。

3、按照拓扑序列遍历DAG的点,对于每个点u,遍历其所有的出边<u,v>,如果dist[v] > dist[u ] + Map[u][v],那么dist[v] > dist[u ] + Map[u][v]。

此方法可以处理负权边。

题目: poj3249    

图片 3图片 4

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 const int N = 100010, M =1100010, INF=0x3f3f3f3f;
 8 struct node
 9 {
10     int to, w, next;
11 };
12 node edge[M];
13 int ind[N], head[N], dist[N], que[N], cost[N];
14 //Èë¶È
15 int iq, ans;
16 void topo(int n)
17 {
18     int i,k;
19     iq=0;
20     memset(que,0,sizeof(que));
21     for(i=1;i<=n;i++)
22         if(ind[i]==0) que[iq++]=i;
23     for(i=0;i<iq;i++)
24     {
25         for(k=head[que[i]]; k!=-1; k=edge[k].next)
26         {
27             ind[edge[k].to]--;
28             if(ind[edge[k].to]==0)
29                 que[iq++]=edge[k].to;
30         }
31     }
32 }
33 void DAG(int n)
34 {
35     int i,k;
36     ans=-INF;
37     for(i=1;i<=n;i++) dist[i]=-INF;// -INF
38     dist[n]=0;
39     for(i=0;i<iq;i++)
40     {
41         int flag=1;
42         for(k=head[que[i]];k!=-1;k=edge[k].next)
43         {
44             flag=0;
45             if(dist[edge[k].to]<dist[que[i]] + edge[k].w)
46                 dist[edge[k].to]=dist[que[i]] + edge[k].w;
47         }
48         if(flag) ans=max(ans,dist[que[i]]);
49     }
50 }
51 void addedge(int i,int j,int k,int w)
52 {
53     edge[k].to=j;
54     edge[k].w=w;
55     edge[k].next=head[i];
56     head[i]=k;
57 }
58 int main()
59 {
60     //freopen("test.txt","r",stdin);
61     int n,m,i,j,k,t;
62     while(scanf("%d%d",&n,&m)!=EOF)
63     {
64         memset(head,-1,sizeof(head));
65         memset(ind,0,sizeof(ind));
66         for(i=1;i<=n;i++) scanf("%d",&cost[i]);
67         for(k=0;k<m;k++)
68         {
69             scanf("%d%d",&i,&j);
70             ind[j]++;
71             addedge(i,j,k,cost[j]);
72         }
73         for(i=1;i<=n;i++)
74             if(ind[i]==0)
75             {
76                 ind[i]=1;
77                 addedge(n+1,i,k++,cost[i]);
78             }
79         topo(n+1);
80         DAG(n+1);
81         printf("%d\n",ans);
82     }
83     return 0;
84 }

View Code

 

 

六、最小环

用Floyd求最小环

Poj1734 Sightseeing trip

Hdu1599

传送门:http://www.cnblogs.com/Potato-lover/p/3954124.html

 

 

admin

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注