Dijkstra的定向或无向图算法？

Question

Dijkstra的定向或无向图算法？

我一直试图谷歌这个,但我发现的结果只是增加了我的困惑.它似乎可以用于两者？如果是这样,它是默认设计的,需要改变什么才能使其以非默认方式工作(无论是定向还是非定向)？

编辑:作为参考,上个学期我有一个问题,我得到了这样的列表(机场):

AER,KZN,1.8835
ASF,KZN,1.3005
ASF,MRV,1.1204
CEK,KZN,1.9263
CEK,OVB,1.6733
DME,KZN,1.7892
DME,NBC,2.2319
DME,UUA,2.3786
EGO,KGD,1.4649
EGO,KZN,1.2603
GYD,NBC,2.0755

Run Code Online (Sandbox Code Playgroud)

有人告诉我它被指示,并要求找到最短的路径.我把它放到我在Github上发现的Dijkstra算法中(这是一个开放计算机中期,所以我们没有足够的时间从头开始编写算法)而我的教授说它返回的最短路径是不正确的,它是甚至没有可能的路径,因为该列表应该是定向的.我不确定我是否应该修改算法或列表以进行此更正.结果是它返回的第二条最短路径实际上是定向最短路径,但我仍然想知道问题是什么.

Answer 1

Kei*_*wan 29

它可以应用于两者.原因如下:

的无向图是基本相同的定向与图双向连接的节点之间的连接(=在相反方向上的两个连接).

因此,您不需要做任何事情来使其适用于无向图.您只需要通过例如邻接列表了解每个给定节点可以到达的所有节点.

好吧,这听起来像你发现的实现将列表中的条目解释为无向,这不是你想要的,所以你应该自己实现算法.我所知道的通常只使用邻接列表(这是一个列表,其中包含有关您可以从给定节点到达哪些节点的信息*=>连接被定向*).这就是为什么我说你不必做任何事情来使其适用于无向图,但是,如果你的算法出于某种原因自动将连接解释为双向的,则需要对其进行更改. (2认同)
但是 Dijkstra 和 Prim/Kruskal 计算了两个本质上不同的东西。Dijkstra 从*一个*节点计算最短路径树，而Prim/Kruskal计算*所有*节点之间的最小生成树。没有为有向图定义 MST 的概念 - 连接必须是无向的。对于有向图，您将寻找最低成本中止，这是使用 Prim/Kruskal 无法完成的。不过，这与 Dijkstra 无关。最短路径树的概念为有向图定义得很好，这就是为什么 Dijkstra 也适用于它们的原因。 (2认同)

Answer 2

Aar*_*ski 5

有向图仅意味着连接顶点的边能够以一种方式连接，但不能以另一种方式连接。这意味着一个顶点可以与另一个顶点相邻，但其他顶点可能不与第一个顶点相邻。

在 Dijkstra 算法的上下文中，图是有向的还是无向的并不重要。Dijkstra 算法只是引用顶点的相邻顶点。如果要将图从有向更改为无向，则必须修改此邻接表。

Answer 3

小智 5

Djikstras 算法通常用于正加权图。也许您将它与广度优先搜索 (BFS) 算法混淆，该算法本质上是用于未加权图的 Djikstras。区别（Djikstras 和 BFS 之间）在于，当您处理加权路径时，我们现在必须考虑路径成本调整（权重）以及在当前之后访问哪些节点的决定。

Answer 4

Mat*_*nny 5

您可以在有向图和无向图中使用Dijkstra算法,因为当您有从边缘列表前往的边时,只需将边添加到PriorityQueue中.例如,如果我的一个节点具有从A到B的权重3的边缘,那么如果它从BI指向将无法将边缘添加回A,而从AI可以将其添加到B.

像其他答案一样,请确保您不要将它与重量混淆.Dijkstra的算法在正加权图上运行,否则优先级队列将无用.

在您的示例中,Dijkstra的算法将起作用,因为图形既有权重(正向)又具有有向边缘.

错误可能是边缘已经以无向图的形式被双重分配.将开头边缘解析为对象时要小心,不要复制邻接列表中的边缘.

归档时间：	9 年，6 月前
查看次数：	27111 次
最近记录：	6 年，5 月前