首页 > 代码库 > 《啊哈！算法》第6章最短路径

《啊哈！算法》第6章最短路径

2024-07-09 07:01:04   221人阅读

第一节 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;}
floyd最短路径算法

 第二节 Dijkstra算法-通过边实现松弛


联系
我们