最短路、path 和 walk在最短路径里我们通常想找从s 到t 的一条总代价最小的路线。如果所有边权非负Dijkstra 可以用贪心方式逐步确定当前最短的点如果存在负权边Dijkstra 的前提会坏掉但 Bellman-Ford 仍然可以通过多轮松弛处理。于是看上去最长路径也可以类似地定义从s 到t找一条边权总和最大的路线。最短路径的松弛是如果[][](,)d[v]d[u]w(u,v) 就更新那么最长路径似乎只要改成如果[][](,)d[v]d[u]w(u,v) 就更新。这个想法只在某些受限场景下成立。在图论里path 和 walk 是有区别的。walk 只要求相邻顶点之间有边可以重复经过顶点和边simple path 则不允许重复经过顶点。中文里都可能被叫作“路径”。日常说“从 A 到 B 的路径”通常不太区分是否允许重复经过同一个点。但图论和算法里这个区别非常关键。通常提到最短路径问题算法求解的是 walk即允许重复。从实现上看常见的最短路算法通常并不会在状态里记录“已经访问过哪些顶点”。Dijkstra 的状态是到每个点的当前最短距离Bellman-Ford 也是不断对边做松弛。它们并没有显式禁止一条候选路线重复经过某个点。最短路能转化成最长路吗在最短路径场景下如果是正权图那么 path 还是 walk 没有区别因为一定不会重复走边浪费权重。若有负数边但不成环那么 Bellman-Ford 仍可处理。但最短路径怕负权环在无向图里则是一条负边就够因为绕一圈代价更小可以一直降到任意低答案不存在反过来最长 walk 怕的是正权环因为绕一圈收益更大可以一直涨到∞∞。这和最短路径里的负权环是对称的。所以反过来看只要图里存在正环在无向图里则是有正边权并且允许重复行走那么最长 walk 就会变成无界问题。并不能简单的转化就行了。不过如果不存在会影响答案的正权环比如全图权重都是负数这时最长路就确实可以转化成最短路了。做法很简单。把每条边的权重()w(e) 变成−()−w(e)原图中的最长 walk 就对应新图中的最短 walk。原图里的正权环会变成新图里的负权环因此可以用 Bellman-Ford 的负权环检测逻辑处理。最长 simple path 是另一个问题那如果要求解的是最长简单路径呢从s 到t找一条不重复经过顶点的路径使得总权重最大。这个定义避免了正权环导致的无穷大。即使图里有正权环由于不能重复经过顶点也不可能无限绕圈。问题总是有有限答案。但这个问题要困难得多。最短路算法之所以能只维护[]d[v]是因为到达v 之后过去怎么来的通常可以被压缩成一个距离值。最长 simple path 不行。你到达v 时已经访问过哪些点会决定后面还能走哪些边。两个状态即使当前顶点相同只要访问集合不同后续空间也可能完全不同。如果把访问集合也放进状态可以做类似动态规划的搜索但状态数量通常是指数级的。这个问题可以和 Hamiltonian Path 规约。给定一个无权图如果它有n 个顶点那么它存在一条长度为−1n−1 的 simple path当且仅当它存在一条经过所有顶点一次的 Hamiltonian path。假如我们能高效求出一般图上的最长 simple path就能判断 Hamiltonian Path 是否存在。后者是 NP-complete 问题因此一般图上的最长 simple path 是 NP-hard 的。所以“最长路径可以取负变成最短路径”这句话只有在特定语义下成立。它不能拿来解决一般图上的最长简单路径。反过来我们还发现如果最短路也强制只能选 simple path那么有负环时它也不能做会变成困难问题。image总结最短路无负环则可用经典算法求解且求出的既是最短 path 也是最短 walk有负环则经典算法求出的 walk 不存在会任意小、path 存在但是求解困难最长路也一样但他不能处理的是正环特例DAG重要例外是 DAG也就是有向无环图。在 DAG 上没有环walk 和 simple path 的区别基本消失也不会出现通过绕正权环把答案刷到无穷大的情况。这时最长路径可以按拓扑序做动态规划。设[]dp[v] 表示从起点s 到v 的最长路径长度那么对每条边(,)(u,v) 做类似[]max([],[](,))dp[v]max(dp[v],dp[u]w(u,v)) 的更新即可。因为拓扑序保证处理v 之前所有可能到达v 的前驱都已经处理过了。