首页 > 代码库 > 图的第k短路
图的第k短路
【问题描述】
给你一个有向图，求从1到n的第k短路。
【解法】
SPFA+A*搜索。
1 A*算法
A*算法在人工智能中是一种典型的启发式搜索算法，启发中的估价是用估价函数表示的：
h(n)=f(n)+g(n)
其中f(n)是节点n的估价函数，g(n)表示实际状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。另外定义h‘(n)为n到目标节点最佳路径的实际值。如果h‘(n)≥h(n)则如果存在从初始状态走到目标状态的最小代价的解，那么用该估价函数搜索的算法就叫A*算法。
2 第K最短路的算法
我们设源点为s，终点为t，我们设状态f(i)的g(i)为从s走到节点i的实际距离，h(i)为从节点i到t的最短距离，从而满足A*算法的要求，当第K次走到f(n-1)时表示此时的g(n-1)为第K最短路长度。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #include<ctime> 7 #include<algorithm> 8 #include<queue> 9 #define MAXN 20100 10 #define INF 1000100000 11 #define pii pair<int,int> 12 using namespace std; 13 struct node{int y,next,v;}e1[MAXN],e2[MAXN]; 14 struct node2 15 { 16 int f,g,id; 17 friend bool operator < (node2 a,node2 b) 18 { 19 return a.f>b.f; 20 } 21 }; 22 int n,m,k,len1,len2,Link1[MAXN],Link2[MAXN],dis[MAXN],vis[MAXN],tim[MAXN],ans[MAXN]; 23 priority_queue<node2>Q; 24 inline int read() 25 { 26 int x=0,f=1; char ch=getchar(); 27 while(!isdigit(ch)) {if(ch==‘-‘) f=-1; ch=getchar();} 28 while(isdigit(ch)) {x=x*10+ch-‘0‘; ch=getchar();} 29 return x*f; 30 } 31 void insert(int xx,int yy,int vv) 32 { 33 e1[++len1].next=Link1[xx]; 34 Link1[xx]=len1; 35 e1[len1].y=yy; 36 e1[len1].v=vv; 37 e2[++len2].next=Link2[yy]; 38 Link2[yy]=len2; 39 e2[len2].y=xx; 40 e2[len2].v=vv; 41 } 42 void SPFA() 43 { 44 priority_queue<int,vector< int >,greater< int > >q; 45 memset(dis,50,sizeof(dis)); 46 dis[1]=0,vis[1]=1,q.push(1); 47 while(!q.empty()) 48 { 49 int tn=q.top(); 50 vis[tn]=0; 51 q.pop(); 52 for(int i=Link2[tn];i;i=e2[i].next) 53 { 54 int tmp=e2[i].y; 55 if(dis[tmp]>dis[tn]+e2[i].v) 56 { 57 dis[tmp]=dis[tn]+e2[i].v; 58 if(!vis[tmp]) 59 { 60 vis[tmp]=1; 61 q.push(tmp); 62 } 63 } 64 } 65 } 66 } 67 void Astar() 68 { 69 if(dis[n]==INF) return; 70 node2 temp; temp.g=0,temp.f=dis[n],temp.id=n; 71 Q.push(temp); 72 while(!Q.empty()) 73 { 74 temp=Q.top(); Q.pop(); 75 if(temp.id==1) {ans[++ans[0]]=temp.f; if(ans[0]>k) return;} 76 for(int i=Link1[temp.id];i;i=e1[i].next) 77 { 78 node2 opt; 79 opt.g=temp.g+e1[i].v; 80 opt.f=opt.g+dis[e1[i].y]; 81 opt.id=e1[i].y; 82 Q.push(opt); 83 } 84 } 85 } 86 int main() 87 { 88 n=read(); m=read(); k=read(); 89 for(int i=1;i<=m;i++) 90 { 91 int x=read(),y=read(),v=read(); 92 insert(x,y,v); 93 } 94 SPFA(); 95 Astar(); 96 for(int i=1;i<=k;i++) 97 { 98 if(!ans[i]) printf("-1\n"); 99 else printf("%d\n",ans[i]);100 }101 return 0;102 }
图的第k短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。