约 10 分钟
Bellman-Ford 是能处理负权边的单源最短路。它反复对所有边做松弛：if(d[u]+w<d[v]) d[v]=d[u]+w;。对 n 个点，最多松弛 n-1 轮即可让所有最短路收敛，复杂度 O(n·m)。
if(d[u]+w<d[v]) d[v]=d[u]+w;
n 个点的图，Bellman-Ford 最多需要松弛几轮？
登录 后可看答案