在这求第 k 短路用的是，A*+dij 所谓的A* 是一种启发式搜索，他给搜索选定一定的方向，避免了，无谓的搜索，如何来确定搜索的顺序？..也就是用一个值来表示这个值为f[x]..每次搜索取f[x]最小的拓展...那么这个f[x]=h[x]+g[x]其中这个h[x]就是当前搜索时的代价..如求K段路这个就是前一个点的h[x']+边的长度...而g[x]是一个估价函数..估价函数要小于是对当前点到目标的代价的估计..这个估计必须小于等于实际值~~否则会出错...A*的关键也就是构造g[x]..，我们的dij 算法。最短路是，就是一种 A* 搜索，其中 g[x]=0;
而这里要说的求K短路一种方法..就是用BFS+A*来搜索的过程...g[x]的设定为到这个点到目标点的最短路（这个可以用dij 一次求出） 径...显然其实小于等于实际值的...h[x]就是搜索到这个点的代价（及走过的路程）..用一个优先队列来做..每次取出h[x]+g[x]最小的点来拓展...拓展 也就是通过这点来更新其能直接经过一条边到达的点..这里做好一个新点就丢进优先队列里去..反正总会从对首弹出h[x]+g[x]最小的点..
首先，我们在放优先队列的是这样的节点，他包括，从原点 到达本节点 的路径长度 len ，然后我们在优先列里，按照 len +dis[i] （dis 到达终点的最最短路）的最小，优先级 排队，
那么当我们第一次搜索到 E 点时，这时肯定是 最短路径，第二次取出的，就是第二短路，以此类推，
struct cnode
{int u;int len;cnode (int uu,int ww):u(uu),len(ww){}friend bool operator < (cnode a,cnode b){return a.len+dis[a.u]>b.len+dis[b.u];}
};
我们从一个点，如何扩展的下一个点呢，就是，将与相连的点 ，入队列，（ 这样 就会走重复的边 ）
队列里面的节点就是，原点 经过 len 的路经 所到达的状态
1 int A_star(int s)
2 {
3 int i;
4 if(dis[s]==inf)return -1;//这个一定要有，若s到t不连通的话，下面会 死循环
5 priority_queue<cnode>que;
6
7 CL(tol,0);
8 que.push(cnode(s,0));
9 while(!que.empty())
10 {
11 cnode a=que.top();que.pop();
12 int u=a.u;
13 int len=a.len;
14 tol[u]++;
15 if(tol[t]==k)return len;
16
17 for(i=0;i<g[u].size();i++)
18 {
19 node b=g[u][i];
20 int v=b.u;
21 que.push(cnode(v,len+b.w));
22 }
23
24 }
25 return -1;
26 } 那要是本身就不存在K短路呢？？那就是e拓展不到K但是其他点很有可能一直打圈圈无限下去...这里就要用个条件来判断一 下...首先在找某个点作为优先队列头出现了几次就用了一个计数器times[]..所求的点times[e]==k就代表得到了解..如果当前想拓展的 点times[]>k就没必要拓展了..因为这个点已经是求到k+1短路了..从这个点继续往下搜肯定得到的是大于等于k+1短路的路径...就像 1->2有3条路..2->3有2条路..那1->3有6条路的概念差不多..没必要对其进行拓展了..
注意 ：
若是 有向边时，我们求 到终点的最短距离时，要将边 反向
poj 2449 Remmarguts' Date （有向边）
http://poj.org/problem?id=2449
求任意两点的第 k 短路
View Code 1 #include<stdio.h>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<map>
9 #define Min(a,b) a>b?b:a
10 #define Max(a,b) a>b?a:b
11 #define CL(a,num) memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 1030
14 #define eps 1e-6
15 using namespace std;
16
17 struct node
18 {
19 int u;
20 int w;
21 node (int uu,int ww):u(uu),w(ww){}
22 };
23 vector<node>g[maxn],rg[maxn];
24 int dis[maxn],vis[maxn],tol[maxn];
25 struct cnode
26 {
27 int u;
28 int len;
29 cnode (int uu,int ww):u(uu),len(ww){}
30 friend bool operator < (cnode a,cnode b)
31 {
32 return a.len+dis[a.u]>b.len+dis[b.u];
33 }
34 };
35 int n,m,s,t,k;
36 void spfa(int s)
37 {
38 int i;
39 for(i=0;i<=n;i++)
40 {
41 dis[i]=inf;
42 vis[i]=0;
43 }
44 dis[s]=0;
45 queue<int>que;
46 que.push(s);
47 while(!que.empty())
48 {
49 int u=que.front();que.pop();
50 vis[u]=0;
51 for(i=0;i<rg[u].size();i++)
52 {
53 node b=rg[u][i];
54 int v=b.u;
55 if(dis[v]>dis[u]+b.w)
56 {
57 dis[v]=dis[u]+b.w;
58 if(!vis[v])
59 {
60 vis[v]=1;
61 que.push(v);
62 }
63 }
64 }
65 }
66
67 }
68 int A_star(int s)
69 {
70 int i;
71 if(dis[s]==inf)return -1;//
72 priority_queue<cnode>que;
73
74 CL(tol,0);
75 que.push(cnode(s,0));
76 while(!que.empty())
77 {
78 cnode a=que.top();que.pop();
79 int u=a.u;
80 int len=a.len;
81 tol[u]++;
82 if(tol[t]==k)return len;
83
84 for(i=0;i<g[u].size();i++)
85 {
86 node b=g[u][i];
87 int v=b.u;
88 que.push(cnode(v,len+b.w));
89 }
90
91 }
92 return -1;
93 }
94 int main()
95 {
96 int i,x,y,z;
97 while(scanf("%d%d",&n,&m)!=EOF)
98 {
99 for(i=0;i<=n;i++)g[i].clear();
100 for(i=0;i<m;i++)
101 {
102 scanf("%d%d%d",&x,&y,&z);
103 g[x].push_back(node(y,z));
104 rg[y].push_back(node(x,z));
105 }
106 scanf("%d%d%d",&s,&t,&k);
107 if(s==t)k++;
108 spfa(t);
109 int ans=A_star(s);
110 cout<<ans<<endl;
111
112
113
114 }
115 }
poj 3255 Roadblocks
求 1到 n 的次短路
View Code 1 #include<stdio.h>
2 #include<iostream>
3 #include<algorithm>
4 #include<cstring>
5 #include<cmath>
6 #include<queue>
7 #include<set>
8 #include<map>
9 #define Min(a,b) a>b?b:a
10 #define Max(a,b) a>b?a:b
11 #define CL(a,num) memset(a,num,sizeof(a));
12 #define inf 9999999
13 #define maxn 5030
14 #define eps 1e-6
15 using namespace std;
16 int n,k,m;
17 int dis[maxn],tol[maxn],vis[maxn];
18 struct node
19 {
20 int u;
21 int w;
22 node (int uu,int ww):u(uu),w(ww){}
23 };
24 vector<node>g[maxn];
25 struct anode
26 {
27 int u;
28 int len;
29
30 anode (int uu ,int w):u(uu),len(w){}
31
32 friend bool operator < (anode a, anode b)
33 {
34 return a.len+dis[a.u]>b.len+dis[b.u];
35 }
36 };
37 void SPFA(int x)
38 {
39 int i;
40 for(i=0;i<=n;i++)
41 {
42 dis[i]=inf;
43 vis[i]=0;
44 }
45
46 dis[n]=0;
47 queue< int >que;
48 que.push(n);
49 vis[n]=1;
50 while(!que.empty())
51 {
52 int u = que.front();que.pop();
53
54
55 vis[u]=0;
56 for(i=0;i<g[u].size();i++)
57 {
58 node b=g[u][i];
59 int v=b.u;
60 if(dis[v]>dis[u]+b.w)
61 {
62 dis[v]=dis[u]+b.w;
63
64 if(!vis[v])
65 {
66 vis[v]=1;
67 que.push(v);
68
69 }
70 }
71 }
72 }
73
74 //for(i=1;i<=n;i++)printf("%d ",dis[i]);
75 //printf("\n");
76
77
78 }
79 int A_star(int s)
80 {
81 int i;
82
83 if(dis[s]==inf)return -1;
84 priority_queue<anode>que;
85
86 CL(tol,0);
87 que.push(anode(1,0));
88 while(!que.empty())
89 {
90
91 anode a=que.top();que.pop();
92 int u=a.u;
93 int len=a.len;
94 tol[u]++;
95 if(tol[n]==k)return len;
96 for(i=0;i<g[u].size();i++)
97 {
98 node b=g[u][i];
99 int v=b.u;
100 que.push(anode(v,len+b.w));
101
102
103 }
104 }
105 return -1;
106
107 }
108 int main()
109 {
110 int i,x,y,z;
111 while(scanf("%d%d",&n,&m)!=EOF)
112 {
113 k=2;
114 for(i=0;i<m;i++)
115 {
116 scanf("%d%d%d",&x,&y,&z);
117 g[x].push_back(node(y,z));
118 g[y].push_back(node(x,z));
119
120 }
121 SPFA(n);
122 int ans=A_star(1);
123 cout<<ans<<endl;
124
125 }
126 }
转载于:https://www.cnblogs.com/acSzz/archive/2012/07/31/2616268.html