找到最短路径的距离中包含最多两个负边的图 [英] Finding shortest path distances in a graph containing at most two negative edges

问题描述

我给定一个有向图，其中每个边缘具有的事实，有在图中最多有两个负边缘的cost.Taking优点，我的目标是找到从给定节点s最短路径的距离到所有节点在五，该算法的时间复杂度应 O（| E | + | V | *登录| V |），所以我想我需要申请Dijkstra算法。

I am given a directed graph where each edge has a cost.Taking advantage of the fact that there are at most two negative edges in the graph, my goal is to find shortest path distances from a given node s to all the nodes in V. The time complexity of the algorithm should be O(|E| + |V|*log|V|), so I think I need to apply Dijkstra's algorithm.

我猜测我需要以某种翻译我给定的图到一个新的图与非负权重，在该曲线图中的最短路径从s到v将相当于在给定的图形所需的最短路径..或也许我需要修改Dijkstra算法？

I am guessing that I need to translate my given graph somehow to a new graph with non-negative weights that a shortest path from s to v in this graph will be equivalent to the required shortest path in the given graph.. or maybe I need to modify Dijkstra's algorithm?

我挣扎现在。任何帮助将是AP preciated！

I am struggling right now. Any help would be appreciated!

推荐答案

由于Dijkstra算法是贪婪的，所以不会有负权重的工作。你需要一些其他的算法如在 Bellman-Ford算法​​ < /一>用于此目的。

Since Dijkstra's algorithm is greedy, it won't work with negative weights. You need some other algorithm like the Bellman-Ford Algorithm for this purpose.

不过，如果你仍想使用Dijkstra算法，有一种已知的方法。在这种方法中，你需要重新分配成本，让一切变得积极。

But, if you still want to use Dijkstra's algorithm, there is a known way. In this method, you need to reassign costs, so that all become positive.

有关，你可以看看约翰逊的算法。约翰逊的算法由以下几个步骤（从维基百科采取）的：

For that you can check out Johnson's Algorithm. Johnson's algorithm consists of the following steps (taken from Wikipedia):

1. 首先，将新的节点q被加入到图中，由零重量连接边缘到每个其它节点的
2. 其次，Bellman-Ford算法​​的情况下，从所述新顶点●起动，以找到每个顶点v的最小重量小时（ⅴ）从●至V A路径的。如果这一步检测到负周期内，算法被终止。
3. 接下来原始图的边使用由Bellman-Ford算法​​计算出的值重新加权：从u到v的边缘，具有长度瓦特（U，V），给出新的长度瓦特（U，V） + H（U） - H（V）
4. 最后，q被除去，并且Dijkstra算法是用于找到在重新加权图中每个顶点从每个节点s的最短路径。

这篇关于找到最短路径的距离中包含最多两个负边的图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！