三重for循环实现图任意两点最短路径
#include<iostream>
using namespace std
;
#define rep(i,a,b) for(int i=a;i<=b;i++)
const int INF
=50;
int n
,m
;
int a
[11][11];
int main
(){
cin
>>n
>>m
;
rep(i
,1,n
)
rep(j
,1,n
){
if(i
==j
)
a
[i
][j
] =0;
else
a
[i
][j
] =INF
;
}
for(int i
=1;i
<=m
;i
++){
int x
,y
,value
;cin
>>x
>>y
>>value
;
a
[x
][y
]= value
;
}
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=n
;j
++)
for(int k
=1;k
<=n
;k
++){
a
[j
][k
] = min(a
[j
][i
]+a
[i
][k
],a
[j
][k
]);
}
for(int i
=1;i
<=n
;i
++){
for(int j
=1;j
<=n
;j
++)
cout
<<a
[i
][j
]<<" ";
cout
<<endl
;
}
}
输入： 6 8 1 2 1 2 3 1 2 4 7 3 4 8 4 5 4 2 6 2 6 4 3 3 5 15
主要原理： A,B两点，添加一点C，影响到了dis（AB）就刷新为 dis（AB）=dis（AC）+dis（CB）; ps： 在点3和点5连接一条长15的边
分析一下：1-5=1-2-6-4-5最短路径是如何实现！？ 那么三重for循环怎么实现两点最短路径呢？ 一：以点6为例，当前2到4dis是7，添加了6，是的2到4的dis是5，更小了，替换他。 二：以点4为例， 没4点是，2到5的dis是1+15=16.添上ta，哎嘿2到5距离更小了 替换他。 发现没， 添加前是没有点6的中间路径（2-4），加上点6后对其它路径有影响修改 为（2-6-4），每次修改依据是啥呢？当然是改后路径比之前更短咯。 点4也是如此。 然后我们看: 我们在找1-5的最短路径时（起初我们不知道1-5怎么连是最短的），我们只有不断寻找两点间路径最短值，然后 将他们拼接起（拼积木一样），最后连成一条完整的1-2-6-4-5的最短路径。 这不就1-5的最短路径顺利得出来了.
