首页 > 代码库 > 最短路径模板总结
最短路径模板总结
dis[u][v]=w[u][v]||0x7ffffffff; for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) { if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j]; } /*Floyed-Warshall*/ b[s]=1;c[s]=1; for(i=1;i<=n-1;i++){ k=0; minl=maxx; for(j=1;j<=n;j++) { if(!b[j]&&f[i][j]<minl) { k=j; minl=f[i][j]; } if(k==0) break; b[k]=1; for(i=1;i<=n;i++) if(c[k]+f[k][j]<c[j]) c[j]=c[k]+f[k][j]; } } /*dijkstra*/ dis[i-n]=oo; dis[s]=0; for(int i=1;i<=n-1;i++) for(int j=1;j<=E;j++) if(dis[u]+w[j]<dis[v]) { dis[v]=dis[u]+w[j]; pre[v]=u;} /*bellman-ford*/ pre[v]=u; pre[s]=0; printf("%d",s); void print(int x) { if(pre[x]==0)return; printf(pre[x]); printf("-->%d",x); } q[1001],tail,head; dis[801]; b[101]; w[1001][1001]//邻接矩阵 a[1001][1001]//出度是多少,出度是谁 dis[s]=0; q[1]=i; tail=1;head=0; b[s]=1; a[i][++a[i][0]]=j; do { head++; head=((head-1)%1001)+1; u=team[head]; b[u]=0; for(int i=1;i<=a[u][0];i++) { if(dis[i]>dis[u]+w[u][a[u][i]]) { dis[i]=dis[u]+w[u][a[u][i]]; if(!b[a[u][j]]) { tail++; tail=((tail-1)%1001)+1; q[tail]=a[u][j]; b[a[u][j]]=1; } } } }while(head!=tail); /*SPFA*/ /*单原点输出路径*/ pre[i][j]=pre[k][j]; pre[a][a]=0; printf("%d",a); int ptint(int x) { if(pre[a][x]==0);return ; print(prea[a][x]); printf("--》%d",pre[a][x]) } /*多原点输出路径*/
我爱我自己?!!
最短路径模板总结
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。