首页 > 代码库 > 最短路模版 (dijkstra&&flody)
最短路模版 (dijkstra&&flody)
1.dijkstra
void dijkstra(int x,int n)//x表示起点,n表示一共的数量{ int min=0,p=0; for(int i=1;i<=n;i++) { dis[i]=map[x][i]; visited[i]=0; } visited[x]=1; for(int i=1;i<=n;i++) { min=inf; for(int j=1;j<=n;j++) { if(!visited[j]&&dis[j]<min) { min=dis[j]; p=j; } } visited[p]=1; for(int j=1;j<=n;j++) { if(!visited[j]&&dis[j]>dis[p]+map[p][j]) dis[j]=dis[p]+map[p][j]; } }}
2.flody
void floyd(){ int i,j,k; for(k=0;k<n;k++) for(i=0;i<n;i++) for(j=0;j<n;j++) if(dis[i][j]>dis[i][k]+dis[k][j]) dis[i][j]=dis[i][k]+dis[k][j];}
个人建议如果在能用dijkstra的地方就尽量用,flody一般会超时。当然如果遇负环的情况的时候就需要用spfa的算法了。
最短路模版 (dijkstra&&flody)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。