首页 > 代码库 > 8月12日————最短路
8月12日————最短路
这个写的很好：http://blog.csdn.net/zhongyanghu27/article/details/8221276
dijkstra算法：
先给出一个无向图
用Dijkstra算法找出以A为起点的单源最短路径步骤如下
算法模板：
void dijkstra(int x){ int i,j; memset(vis,0,sizeof(vis)); for( i=0;i<= max_city;i++ ) dis[i] = map[x][i]; dis[0] = 0; for( i=1;i<=max_city;i++ ) { int p = x,temp = inf; for( j=1;j<=max_city;j++ ) { if( !vis[j] && dis[j] < temp ) { p = j; temp = dis[j]; } } vis[p]=true; for( j=1;j<=max_city;j++ ) { if( map[p][j]!=inf ) { if( dis[j] > dis[p]+map[p][j] ) dis[j] = dis[p]+map[p][j]; } } }}
floyd算法模板
void folyd(){ for(int k = 1 ; k <= n ; k++){/*枚举n个点来更新dis*/ for(int i = 1 ; i <= n ; i++){ for(int j = 1 ; j <= n ; j++) if(dis[i][k] != -1 && dis[j][k] != -1)/*如果在求最大值的时候加上这一句*/ dis[i][j] = min(dis[i][k]+dis[k][j] , dis[i][j]); } } }
训练题目；http://acm.hdu.edu.cn/diy/contest_show.php?cid=24386
8月12日————最短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。