负边与负环：数据结构与算法实验

互动实验 1 / 5

图无环，0→1 权 2、1→2 权 -5、0→2 权 1，到 2 的最短距离是多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<tuple<int,int,int>>edges{{0,1,2},{1,2,-5},{0,2,1}};vector<int>d{0,1000000,1000000};
for(int round=0;round<2;++round)for(auto [u,v,w]:edges)if(d[u]!=1000000)d[v]=min(d[v],d[u]+w);
cout<<d[2]<<" "<<d[1];
}

图无环，0→1 权 2、1→2 权 -5、0→2 权 1，到 2 的最短距离是多少？

思路提示

经过结点 1 的路径长度为 2−5=-3。

可以回到前一步复查示例，理解后再独立验证。

互动实验 2 / 5

到结点 1 的最短距离是多少？

请根据示例独立推演，再提交验证。

C++ 示例 · 按执行顺序推演

#include <bits/stdc++.h>
using namespace std;

int main() {
vector<tuple<int,int,int>>edges{{0,1,2},{1,2,-5},{0,2,1}};vector<int>d{0,1000000,1000000};
for(int round=0;round<2;++round)for(auto [u,v,w]:edges)if(d[u]!=1000000)d[v]=min(d[v],d[u]+w);
cout<<d[2]<<" "<<d[1];
}

到结点 1 的最短距离是多少？

思路提示

唯一到达方式是 0→1。

可以回到前一步复查示例，理解后再独立验证。

互动实验 3 / 5

负边是否必然意味着存在负环？

选择符合算法原理和适用条件的一项。

互动实验 4 / 5

经典 Bellman-Ford 做完 n-1 轮后仍可松弛可达边，说明什么？

选择符合算法原理和适用条件的一项。

互动实验 5 / 5

负环对某个终点最短距离的影响还需检查什么？

选择符合算法原理和适用条件的一项。

负边与负环

准备探索负边与负环

图无环，0→1 权 2、1→2 权 -5、0→2 权 1，到 2 的最短距离是多少？

到结点 1 的最短距离是多少？

负边是否必然意味着存在负环？

经典 Bellman-Ford 做完 n-1 轮后仍可松弛可达边，说明什么？

负环对某个终点最短距离的影响还需检查什么？

引导实验已完成。

把发现，变成独立解决问题的能力。