我得到一个带有权重函数和顶点 s 的有向图。我的目标是找到任何其他顶点 v，即从 s 到 v 的最短路径，它恰好穿过一个负边。该算法的时间复杂度应该是 O(|E| + |V|*log|V|)，所以我想我需要以某种方式使用 Dijkstra 算法。
我猜我需要以某种方式将给定的图转换为具有非负权重的新图，该图中从 s 到 v 的最短路径将等同于给定图中所需的最短路径..或者我需要以某种方式修改 Dijkstra 的算法？
我试着想了一下，现在没有任何想法...... :(
我得到一个带有权重函数和顶点 s 的有向图。我的目标是找到任何其他顶点 v，即从 s 到 v 的最短路径，它恰好穿过一个负边。该算法的时间复杂度应该是 O(|E| + |V|*log|V|)，所以我想我需要以某种方式使用 Dijkstra 算法。
我猜我需要以某种方式将给定的图转换为具有非负权重的新图，该图中从 s 到 v 的最短路径将等同于给定图中所需的最短路径..或者我需要以某种方式修改 Dijkstra 的算法？
我试着想了一下，现在没有任何想法...... :(