1回答

liuyubobobo

2020-03-19

已采纳

你是正确的。

严格来说，我们的实现，计算的是从src到任一顶点，最少经过 k 步的最小路径：也就是基于我们的实现，我们有可能在第k轮松弛操作，求出经过大于k步的最小路径。

举个例子，我们就看这样的一个简单的图：

0 -> 1 -> 2 -> 3

其中0->1的权值为1；1->2的权值为1；2->3的权值为1。起始点为0；终止点为3。

初始：dist[0] = 0; dist[1] = ∞; dist[2] = ∞; dist[3] = ∞。

在这里注意，我们每轮松弛所有的边，都是从顶点为0的边开始松弛的。

第一轮松弛：

首先，松弛0->1这条边，可以松弛，得到：

dist[0] = 0; dist[1] = 1; dist[2] = ∞; dist[3] = ∞；

0相邻的所有边松弛完了，松弛1相邻的边，即松弛1->2，可以松弛，得到：

dist[0] = 0; dist[1] = 1; dist[2] = 2; dist[3] = ∞；

1相邻的所有边松弛完了，松弛2相邻的边，即松弛2->3，可以松弛，得到：

dist[0] = 0; dist[1] = 1; dist[2] = 2; dist[3] = 3；

至此，我们只用了一轮松弛操作，就得到了从0到3的最短路径。但是，注意，我们之所以只用一轮松弛操作，是基于我们在松弛1->2这条边的时候，恰巧0->1这条边刚刚松弛过，使得使得dist[1]不再是∞；同理，我们在松弛2->3这条边的时候，敲好1->2这条边刚刚被松弛过，使得dist[2]不是∞。

---

下面，我们看这个例子：

3 -> 2 -> 1 -> 0

其中3->2的权值为1；2->1的权值为1；1->0的权值为1。起始点为3；终止点为0。

初始：dist[3] = 0; dist[2] = ∞; dist[1] = ∞; dist[0] = ∞。

第一轮松弛：

首先，0没有邻边，看1的邻边。

松弛1->0这条边，不可以松弛，因为dist[1]=∞！

看2的邻边，2->1这条边，不可以松弛，因为 dist[2]=∞！

看3的邻边，3->2这条边，可以松弛，得到：

dist[3] = 0; dist[2] = 1; dist[1] = ∞; dist[3] = ∞

第一轮松弛结束！

第二轮松弛：

首先，0没有邻边，看1的邻边。

松弛1->0这条边，不可以松弛，因为dist[1]=∞！

看2的邻边，2->1这条边，可以松弛，得到：

dist[3] = 0; dist[2] = 1; dist[1] = 2; dist[3] = ∞

看3的邻边，3->2这条边，可以松弛，得到：

dist[3] = 0; dist[2] = 1; dist[1] = 2; dist[3] = ∞ （在这里是一次重复松弛）

第二轮松弛结束！

第三轮松弛：

首先，0没有邻边，看1的邻边。

松弛1->0这条边，现在可以松弛了，得到：

dist[3] = 0; dist[2] = 1; dist[1] = 2; dist[3] = 3

看2的邻边，2->1这条边，可以松弛，得到：

dist[3] = 0; dist[2] = 1; dist[1] = 2; dist[3] = 3（在这里是一次重复松弛）

看3的邻边，3->2这条边，可以松弛，得到：

dist[3] = 0; dist[2] = 1; dist[1] = 2; dist[3] = 3 （在这里是一次重复松弛）

第三轮松弛结束！

至此，三轮松弛后，我们才能得到从3->0的最短路径。

仔细观察，在这个例子里，每一轮结束后，我们得到就是从src(3)到每个顶点，经过k步后所能得到的最短路径。（∞表示不可抵达）

当然，这个例子比较极端。在实际情况下，还有很多情况，都会让松弛操作1轮不能得到最终答案。虽然松弛一轮可能就得到了答案，但也可能无法得到答案。但松弛V-1轮，是一定可以获得最终答案的。这是最保守的情况。你也可以试试，随机生成一个图，然后将松弛1轮后的结果和松弛V-1轮后的结果比较一下。在大多数情况下，应该都是不同的：）

继续加油！：）

4

0