d[i] = max ( d[i], min（d[u], map[u][i]）) d[u]是当前进入访问点集合的点。
S为已访问的点集。

定理 每次加入的S的点u，d[u]就是题目所求最大载重。
证明
每次加入S的点u为当前d值最大的点，所以未访问的点集中没有点可以对u进行松弛操作(若t能对u进行松弛操作，则有d[t]>d[u])。而S中的顶点也都进行了松弛操作，所以D的值不会改变。定理得证。

• Re:用dijkstra解此题的证明 (7) damacheng009 2010-08-08 18:08:39