首页 > 代码库 > 次短路 + 第K短路 模版
次短路 + 第K短路 模版
虽然从字面上看，次短路和第2短路是一样的。但是我在题目中遇到的却不是这样的。
在有些题目中，需要判断次短路是否存在。比如说，u、v之间只有一条路径。那么只有最短路。次短路是不存在的。这时候，解题方法是先求出最短路，然后枚举删除最短路径中的边，然后求最小值。题目可以看poj3986。
第K短路的实现是 SPFA + 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算法。
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短路即可。
如果u、v之间只有一条路径，那么k短路与最短路的值是一样的。还得知道的是，如果u、v之间如果存在一个圈，那么K+1短路比K短路就要多这个圈的边权的和。
K短路的模版如下，时间复杂度不确定，不过能知道已经很高效了。可以去用poj2449测试，只要加头文件和主函数就可以了。
const int N = 1010, M=100010;const int INF = 0x3f3f3f3f;struct node{ int to, w, next;};node edge[M],edge1[M];int head[N], dist[N], outq[N], head1[N], tot;bool vis[N];bool SPFA(int s, int n ){ int i,k; for(i=0;i<=n;i++) dist[i]=INF; memset(vis,0,sizeof(vis)); memset(outq,0,sizeof(outq)); queue<int > q; while(!q.empty()) q.pop(); vis[s]=1; dist[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; outq[u]++; if(outq[u]>n) return 0 ; k=head1[u]; while(k>=0) { if(dist[edge1[k].to]-edge1[k].w>dist[u]) { dist[edge1[k].to]=dist[u]+edge1[k].w; if(!vis[edge1[k].to]) { vis[edge1[k].to]=1; q.push(edge1[k].to); } } k=edge1[k].next; } } return 1;}struct Node1{ int to; int g,f; bool operator<(const Node1 &r) const { if(r.f==f) return r.g<g; return r.f<f; }};int a_star(int start, int End, int k,int n){ Node1 e,ne; int cnt=0; priority_queue<Node1> que; while(!que.empty()) que.pop(); if(start==End) k++; if(dist[start]==INF) return -1; e.to=start; e.g=0; e.f=e.g+ dist[e.to]; que.push(e); while(!que.empty()) { e= que.top(); que.pop(); if(e.to==End) cnt++; if(cnt==k) return e.g; for(int i=head[e.to];i!=-1;i=edge[i].next) { ne.to=edge[i].to; ne.g=e.g+ edge[i].w; ne.f=ne.g+ dist[ne.to]; que.push(ne); } } return -1;}void addedge(int i,int j,int w){ edge[tot].to=j; edge[tot].w=w; edge[tot].next=head[i]; head[i]=tot++;}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(head1,-1,sizeof(head1));}
枚举 + 最短路 实现次短路重要的一步是要用一个前驱来记录最短路径。还需要对属于最短路径的边标记。
const int N = 1010, M=100010;const int INF = 0x3f3f3f3f;struct node{ int u,to, w, next,flag;};node edge[M];int head[N], dist[N], outq[N];bool vis[N];int tot,flag,path[N];bool SPFA(int s, int n ){ int i,k; for(i=0;i<=n;i++) dist[i]=INF; memset(vis,0,sizeof(vis)); memset(outq,0,sizeof(outq)); queue<int > q; while(!q.empty()) q.pop(); vis[s]=1; dist[s]=0; q.push(s); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; outq[u]++; if(outq[u]>n) return 0 ; k=head[u]; while(k>=0) { if(edge[k].flag&&dist[edge[k].to]-edge[k].w>dist[u]) { dist[edge[k].to]=dist[u]+edge[k].w; if(!flag) path[edge[k].to]=k; if(!vis[edge[k].to]) { vis[edge[k].to]=1; q.push(edge[k].to); } } k=edge[k].next; } } return 1;}void addedge(int i,int j,int w){ edge[tot].u=i; edge[tot].to=j; edge[tot].w=w; edge[tot].flag=1; edge[tot].next=head[i]; head[i]=tot++;}void init(){ tot=0; memset(head,-1,sizeof(head)); memset(path,-1,sizeof(path));}可以用poj3986来测试模版，需要记住是要加两条边，正向和反向边。
次短路 + 第K短路 模版