最短路径问题小结

最短路径问题包括：

1、单源最短路。

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

3、次短路和k短路。

4、差分约束系统。

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

6、最小环。

一、单源最短路

算法： Dijkstra 、 Bellman – Ford 、SPFA

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

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

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

题目：

多源转单源 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

 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
",ans);
82     }
83     return 0;
84 }