【参考答案】讨论7.4 Floyd算法与负值圈

<p>如果图中有负值圈，Floyd算法还能用吗？如何知道图中是否存在负值圈？</p><p><br ></p><p>Floyd算法的三重循环中的D[i][j]表示的是i到j的某种距离——不到最后一步，不一定是最短距离；但是只要D[i][j]小于正无穷，就表示i到j存在至少一条路径，而这条路径的长度就是当前的D[i][j]。</p><p><br ></p><p>负值圈意味着从某个顶点i出发，兜了一圈回到i的时候，路径长度是负数。于是很显然有：当我们发现某个D[i][i]变成负数的时候，就意味着出现了负值圈。这里的D[i][i]在计算前应被初始化为0，表示原始图中没有从i到i的自回路。</p><p><br ></p><p>当存在负值圈的时候，圈内顶点之间的最短路实际上是不存在的（长度为负无穷）。而Floyd算法一定在有限多步后停止，所以不可能得到正确的结论。除非在算法中增加一步判断 —— 即在更新了D[i][j]之后，增加判断</p><p><code class="brush:cpp;toolbar:false" >if&nbsp;(&nbsp;i==j&nbsp;&amp;&amp;&nbsp;D[i][j]&lt;0&nbsp;)&nbsp;return&nbsp;ERROR;</code></p><p>（当然Floyd函数也需要改成返回一个计算成功或不成功的标记。）</p><p><br ></p>