一点看法，有错误请及时指出，共同学习:)

1.为什么用PRIM可以做？

我们这样想，把两个台（即起点和终点）有路径的所有生成树都列出来，然后找出一个最小生成树。那么，可以证明最小生成树中两点之间的路径中最长的那条边就是题目所求的。
证明：
我们把所有存在起点终点路径的生成树中起点和终点之间路径的最长值拿出来，记成集合S
那么即证，最小生成树中，连接起点和终点的路径上最长的边K，是S中最短的元素。
假设它不是最短的元素，那么必可以找到另外一条比K还短的元素，将起点和终点连接起来。但这样就与最小生成树的性质矛盾，所以最小生成树中的这条边K，一定是题目所求。

2.为什么floyd可以求
int Floyd()
{
int s,m,d;
for(m=0;m<vex_num;++m)
   for(s=0;s<vex_num;++s)
    for(d=0;d<vex_num;++d)
    {
     if(dis[s][m]<dis[s][d] && dis[m][d]<dis[s][d] )
      dis[s][d]=dis[s][m]>dis[m][d]?dis[s][m]:dis[m][d];
    }
return dis[0][1];
}
FLOYD的代码如上

FLOYD的原理即，对任何两个点S，D，枚举所有的点为中点M，即
S->M,M->D
上面的代码就可以求出连接不同顶点对的路径中最长的边K的最小值(这个有点难理解，我也有点晕)

FLOYD的话，建议用
4
0 0
15 0
5 1
5 2
模拟一下
写着写着发现用FLOYD我自己也不是太懂，坐板凳等大牛来讲- -

• Re:想了一下好像想通了 (265) YA_ME_DE 2009-05-11 22:55:33