本文共 807 字，大约阅读时间需要 2 分钟。

关于原理

需要注意的是：Floyd算法不能解决带有“负权回路”（或者叫“负权环”）的图，因为带有“负权回路”的图没有最短路。例如下面这个图就不存在1号顶点到3号顶点的最短路径。因为1->2->3->1->2->3->…->1->2->3这样路径中，每绕一次1->-2>3这样的环，最短路就会减少1，永远找不到最短路。其实如果一个图中带有“负权回路”那么这个图则没有最短路。 A->B=4 B->A=2

模板

#include
   
    #include
    
     #include
     
      #define MAXN 100#define INF 0x3f3f3f3fusing namespace std;int a[MAXN][MAXN];int n,m;//n表示顶点个数，m表示边的条数void Floyd() {
   	for(int k=1; k<=n; k++) {
   		for(int i=1; i<=n; i++) {
   			for(int j=1; j<=n; j++) {
   				if(a[i][j]>a[i][k]+a[k][j] )					a[i][j]=a[i][k]+a[k][j];			}		}	}}void init() {
   	for(int i=1; i<=n; i++) {
   		for(int j=1; j<=n; j++) {
   			if(i==j)				a[i][j]=0;			else				a[i][j]=INF;		}	}}int main() {
   	cin>>n>>m;	for(int i=1; i<=m; i++) {
   		int t1,t2,t3;		cin>>t1>>t2>>t3;		a[t1][t2]=t3;	}	Floyd();	cout<
     
    
   

转载地址：http://qddcz.baihongyu.com/