首页 > 代码库 > vijos1635 SPFA和FLOYD算法如何打印路径
vijos1635 SPFA和FLOYD算法如何打印路径
之前打的spfa或是floyd都只是用来求最短路,对于如何打印路径问题一点都没有概念
可能也是因为对于原理没有很理解的缘故?
总之,之后赶紧看了一下,现在总算是明白了.....MARK一下自己的理解
早晨碰到了一题挺裸的最短路问题:vijos1635
1.首先说说spfa的方法:
其实自己之前打的最多的spfa是在网格上的那种,也就是二维的
一维的需要邻接表+queue
以及对于queue的操作,自己也是醉了
这里贴一个模板(不含打印路径):
#include<cstdio>#include<cstring>#include<queue>#include<iostream>using namespace std;const int maxn=10100;int n,m,k,t,x,y,s,ans=0;long long tot=0;struct edge{ int from,to,w,next;}e[10100000];int head[maxn],dist[maxn];bool vis[maxn];void add(int x,int y,int z){//邻接表 e[tot].from=x; e[tot].to=y; e[tot].w=z; e[tot].next=head[x]; head[x]=tot++;}void spfa(int s){ queue<int>q; memset(dist,63,sizeof(dist)); memset(vis,false,sizeof(vis));//感觉这里的赋值和二维的略有区别,这里是初始值false q.push(s); dist[s]=0; while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=false;② for(int i=head[u];i!=-1;i=e[i].next){ int v=e[i].to; if(dist[v]>dist[u]+e[i].w){ dist[v]=dist[u]+e[i].w; if(!vis[v]){ //如果已经入队,或是初始值① vis[v]=true; q.push(v); } } } }}int main(){ scanf("%d",&n); memset(head,-1,sizeof(head));//记得head赋值为-1 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&s); if(s!=0){ add(i,j,s); } } spfa(1); printf("%d",dist[n]); return 0;}
好好感受一下①和②
对于spfa打印路径问题:
这里就需要用上指针的思想,去找n的前驱
所以如果dist有更新值,那么就记录下,但是这里要理解,
你记录的并不是根据这条路的路径顺序记的
说白了就是,f[1]并不是第一条路径
而是让v->u,这才是f应该做的
if(dist[v]>dist[u]+e[i].w){ dist[v]=dist[u]+e[i].w;
f[v]=u;//在更新值的后面加上这个
if(!vis[v]){ vis[v]=true; q.push(v); }
}
以及调用一个递归函数寻找前驱:
void printpath(int k){ if(k!=0){ printpath(f[k]); printf("%d ",k); }}
2.FLOYD算法:
也是在更新值后面加上一条语句:
k=1-n
i=1-n
j=1-n
if(..>..)
dist[i][j]=dist[i][k]+dist[k][j];
f[i][j]=f[i][k];
for(v=0; v<n; ++v) { for(w=v+1; w<n; w++) { printf("%d ->%d:%d ",v,w,D[v][w]); k=P[v][w]; /* 获得第一个路径顶点下标 */ printf(" path: %d",v); /* 打印源点 */ while(k!=w) /* 如果路径顶点下标不是终点 */ { printf(" -> %d",k); /* 打印路径顶点 */ k=P[k][w]; /* 获得下一个路径顶点下标 */ } printf(" -> %d\n",w); /* 打印终点 */ } printf("\n"); }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。