说好的写dijkstra 算法堆优化版本的，但是因为，妹子需要，我还是先把Floyd算法写一下吧！啦啦啦！

咳咳，还是说正事吧！

------------------------------------------------说正事专用分隔符------------------------------------------

用一个关系式，表达一下Floyd算法和dijkstra算法之间的关系

是不是很好懂，其实就把dijkstra算法做了n遍，额鹅鹅鹅，也不能说n遍吧，看有多少个点，

每个点轮流做起点，就能便利出所有的最短路的值，话不多说，直接上代码好吧。

问题还是上篇博客的问题（https://www.cnblogs.com/laysfq/p/9808088.html）

 

#include
     
      #include
      
       using namespace std;const int maxint = 10000000;const int maxn = 1000;int x, y, z;int dis[maxn][maxn];int n, m;void floyd() {    for (int k = 1; k <= n; ++k) {   //枚举中间点k        for (int i = 1; i <= n; ++i) {   //枚举端点i            for (int j = 1; j <= n; ++j) {   //枚举端点j                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);            }        }    }}int main() {    while (cin >> n >> m&&n&&m) {        for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= n; ++j) {                dis[i][j] = maxint;            }        }        for (int i = 1; i <= n; ++i) dis[i][i] = 0;        for (int i = 0; i < m; ++i) {            cin >> x >> y >> z;            dis[x][y] = dis[y][x] = z;        }        floyd();    //    cout << dis[1][n] << endl;        for (int i = 1; i <= n; ++i) {            for (int j = 1; j <= n; ++j) {                if(j!=i) cout << "起点"<
       <<"到点" <
        
         << "的最短距离是" << dis[i][j] << endl;            }            cout << endl;        }    }    return 0;}
        
      
     

运行结果如下：

 

 

其实核心还是dijkstra算法，所以这个算法没什么好讲的了，那么就到这了哦！

赶紧教妹子写代码去，哈哈！