首页 > 代码库 > 《啊哈!算法》第6章最短路径
《啊哈!算法》第6章最短路径
第一节 Floyd-Warshall算法
本算法可以求任意两个点之间的最短路径,又称“多源最短路径”,其时间复杂度为O(n^3)
其核心部分只有下面几行,注意加法的溢出处理
//floyd最短路径算法的核心部分 for(int k = 0; k < n; ++ k){ for(int i = 0 ; i < n ; ++ i){ for(int j = 0 ; j < n ; ++ j){ if(grid[i][k]!=INT_MAX && grid[k][j]!=INT_MAX &&grid[i][j] > grid[i][k]+grid[k][j]){ grid[i][j] = grid[i][k] + grid[k][j]; path[i][j] = k; } } } }
/* *基于有向图的floyd最短路径算法 *floyd算法不能解决带有“负权回路”的图 */#include <iostream>#include <vector>#include <algorithm>#include <climits>#include <cstdio>using namespace std;typedef vector<vector<int> > VVI;void floyd(VVI& grid, VVI& path){ int n = grid.size(); //floyd最短路径算法的核心部分 for(int k = 0; k < n; ++ k){ for(int i = 0 ; i < n ; ++ i){ for(int j = 0 ; j < n ; ++ j){ if(grid[i][k]!=INT_MAX && grid[k][j]!=INT_MAX &&grid[i][j] > grid[i][k]+grid[k][j]){ grid[i][j] = grid[i][k] + grid[k][j]; path[i][j] = k; } } } }}void print(int x, int y, VVI& path){ int k = path[x][y]; //cout<<"k="<<k<<endl; if(k==-1) return; print(x,k,path); printf("%d->",k); print(k,y,path);}int main(){ int n,m; cin >> n >> m; VVI grid(n,vector<int>(m,INT_MAX)); for(int i = 0 ; i < n; ++ i) grid[i][i] = 0; for(int i = 0 ; i < m; ++ i){ int a,b,e; cin >> a >> b >> e; grid[--a][--b] = e; } VVI path(n,vector<int>(m,-1)); floyd(grid,path); //输出最终的结果 cout<<string(30,‘=‘)<<endl; printf("start\tend\tlength\tpath\n"); for(int i = 0 ; i < n ; ++ i){ for(int j = 0 ; j < n; ++ j){ printf("%4d\t%4d\t%4d\t",i+1,j+1,grid[i][j]); printf("%d->",i+1); print(i,j,path); printf("%d\n",j+1); } //printf("\n"); } cout<<string(30,‘=‘)<<endl; return 0;}
第二节 Dijkstra算法-通过边实现松弛
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。