我能用Dijkstra算法处理负权图吗？
我知道Bellman-Ford算法可以很好地处理负权重图，但我开发了一个Dijkstra算法代码，它工作得非常好。但当我插入负加权边时，它失败了。有解决办法吗？
共有3个答案
如你所说，Bellman Ford是在负重图中寻找最短路径的首选算法。在这种情况下使用Dijkstra算法的问题是Dijkstra假设图中从s到t的所有可能的子路径都必须小于目标子路径，当添加负边权重时，这不一定是真的。
事实上，在特殊情况下是可能的。如果存在负长度的边，Dijkstra算法将失败。但是，如果所有边的长度均为负值，则可以反转所有边的长度，并使用该算法查找图形两个顶点之间的最长路径（该路径将表示原始图形中的最短路径）。
但在一般情况下，正如你所说的，不可能使用Dijkstra。如果没有负长度的循环，则应使用Bellman-Ford算法。如果你不能保证没有负长度的循环，那么这个问题就是NP完全问题，并且没有已知的多项式算法。
我认为我们不能这样做，因为Dijkstra算法无法找到到达目标顶点的最终方法，因为它可能会卡在循环中，它不是为负权重图设计的，您应该使用bellman-ford算法
-
我说的只是边缘，而不是负权重循环。
-
假设我们有一个有向图，它同时包含正加权边和负加权边。 我知道最短路径解决方案是Bellman-Ford算法。 我的问题是：为什么我们不能只是在所有的边成本上增加一些大的值N，这样就不再有负边了，然后使用效率高得多的Dijkstra算法？
-
我们将用于确定最短路径的算法称为“Dijkstra算法”。Dijkstra算法是一种迭代算法，它为我们提供从一个特定起始节点到图中所有其他节点的最短路径。这也类似于广度优先搜索的结果。 为了跟踪从开始节点到每个目的地的总成本，我们将使用顶点类中的 dist 实例变量。 dist实例变量将包含从开始到所讨论的顶点的最小权重路径的当前总权重。该算法对图中的每个顶点重复一次;然而，我们在顶点上迭代的顺序
-
一、迪杰斯特拉算法介绍 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个节点到其他节点的最短路径。 它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。 基本思想 通过Dijkstra计算图G中的最短路径时，需要指定起点s(即从顶点s开始计算)。 此外，引进两个集合S和U。S的作用是记录已求出最短路径的顶点(以及相应的最短路径长度)，而U则是
-
问题内容： 我正在尝试编写Dijkstra的算法，但是我在努力如何在代码中“说”某些事情而苦苦挣扎。为了可视化，这是我要使用数组表示的列： 因此，将有几个数组，如下面的代码所示： 粗体部分是我要坚持的地方-我正在尝试实现算法的这一部分： 3.对于当前节点，请考虑其所有未访问的邻居并计算其暂定距离。 例如，如果当前节点（A）的距离为6，并且将其与另一个节点（B）相连的边为2，则通过A到B的距离将为6
-
我试图使用邻接列表和PQ作为最小堆来实现单目标最短路径的Dijkstra算法。输出必须显示所有顶点到目标顶点的路径，如果路径存在，如果是，它的总和（最短），如果否，否路径。链接到整个代码 输入格式： 第一行是顶点数，n 第二行开始：（从1到n的顶点） 第一列是顶点 之后，多对， 根据GDB，它显示了在提取最小函数时发现的分段故障。 客户. c 从文本中提取输入。txt文件并创建一个有向图 服务器.