前言
如果求出每两点之间的最短路，不必多次调用Dijkstra算法，有一个更简单的算法叫Floyd算法。
基本思想
对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。
tip
调用Floyd算法之前需要做一些简单的初始化，顶点到顶点本身权值为零，其他全部为无穷大。核心代码如下：
for(int k
=1; k
<=n
; k
++)
{
for(int i
=1; i
<=n
; i
++)
{
for(int j
=1; j
<=n
; j
++)
{
if(mp
[i
][k
]+mp
[k
][j
]<mp
[i
][j
])
{
mp
[i
][j
]=mp
[i
][k
]+mp
[k
][j
];
}
}
}
}
完整代码
#include
<bits
/stdc
++.h
>
using namespace std
;
const int inf
=1<<29;
const int
N=100;
int
main()
{
int mp
[N][N],n
,m
,t1
,t2
,t3
;
cin
>>n
>>m
;
for(int i
=1; i
<=n
; i
++)
{
for(int j
=1; j
<=n
; j
++)
{
if(i
==j
)
mp
[i
][j
]=0;
else
mp
[i
][j
]=inf
;
}
}
for(int i
=1; i
<=m
; i
++)
{
cin
>>t1
>>t2
>>t3
;
mp
[t1
][t2
]=t3
;
mp
[t2
][t1
]=t3
;
}
for(int k
=1; k
<=n
; k
++)
{
for(int i
=1; i
<=n
; i
++)
{
for(int j
=1; j
<=n
; j
++)
{
if(mp
[i
][k
]+mp
[k
][j
]<mp
[i
][j
])
{
mp
[i
][j
]=mp
[i
][k
]+mp
[k
][j
];
}
}
}
}
for(int i
=1; i
<=n
; i
++)
{
for(int j
=1; j
<=n
; j
++)
{
printf("%d\t",mp
[i
][j
]);
}
cout
<<endl
;
}
return 0;
}
