最短路径是最经典的必学图论问题。Dijkstra 处理非负权图,Bellman-Ford 可以处理负权边,还能发现负权环。学到这里,很自然会冒出一个问题:既然有最短路径,那有没有最长路径?如果有,能不能把松弛操作里的 min 换成 max ,把最短路径算法改一改就用? 这个问题表面上很对称,实际并不对称。最长路径不是一个“最短路径的反向版本”,而是会逼着我们重新确认“路径”到底允许什么、环怎么处理、答案是否一定有限。 最短路、path 和 walk 在最短路径里,我们通常想找从 \(s\) 到 \(t\)