Floyd算法（任意两点间最短路径）

---

因为时间复杂度为O(n^3)，所以可以使用顶点数为200以内，创建邻接矩阵在空间上也是可以的，而且每个点之间的数据都需要记录，使用邻接矩阵也是很好的。

设计思路：

1. 遍历所有的点k
2. 以该点k为中介点，遍历所有与它相邻的点是否满足dis[i][k]+dis[k][j]<dis[i][j]，满足则覆盖a[i][j]。

如果使用邻接表，则dis[..][k]很难找，需要遍历0-n-1的行才能找到所有的dis[..][k]。
dis[i][j]也是，操作比矩阵要复杂很多。

---

示例代码：

测试数据：
4 5
1 2 1
1 3 2
1 4 5
2 4 3
3 4 1

image.png

主要数据结构：

int dis[N][N]={0};           // 记录到源点的距离
int points=0;                // 记录点数

示例代码：

#include <bits/stdc++.h>
using namespace std;
typedef struct{
  int num;      // 在BFS中第一列[0]中作为记录上次遍历的位置
  int length;    // 长度
}Node;
const int INF=10000000;
#define N 200
int dis[N][N]={0};           // 记录到源点的距离
int points=0;                // 记录点数
int edges=0,begining,ending;
void Floyd(){
  int i,j,k;
  for(k=1;k<points+1;k++){
    for(i=1;i<points+1;i++){
      for(j=1;j<points;j++){
        if(dis[i][k]!=INF&&dis[k][j]!=INF&&dis[i][k]+dis[k][j]<dis[i][j]){
          // 如果同步到i>j的一面会导致实际更改未被打印，所以要把左侧的结果同步到右侧。
          dis[i][j]=dis[i][k]+dis[k][j];
          dis[j][i]=dis[i][k]+dis[k][j];
        }
      }
    }
  }
}
// 为了减少打印操作，只打印右半边的数据
void show(){
  int i,j;
  for(i=1;i<points+1;i++){
    for(j=i+1;j<points+1;j++){
      if(dis[i][j]!=0)
      cout<<"("<<i<<","<<j<<")"<<dis[i][j]<<endl;
    }
  }
}
int main(){
  int i,j;
  scanf("%d %d",&points,&edges);
  for(i=1;i<points+1;i++){
    for(j=1;j<points+1;j++){
      dis[i][j]=INF;
    }
  }
  int point1,point2,length;
  for(i=0;i<edges;i++){
    scanf("%d %d %d",&point1,&point2,&length);
    dis[point1][point2]=length;
    dis[point2][point1]=length;
  }
  Floyd();
  show();
}