Dijkstra 算法是用于有向图还是无向图？
Is Dijkstra's algorithm for directed or undirected graphs?
我一直在尝试 google 这个，但我发现的结果只会让我更加困惑。似乎它可以同时用于两者？如果是这样，默认情况下它是为哪个设计的？需要更改什么才能使其以非默认方式工作（无论是定向还是非定向）？
编辑：作为参考，上学期我遇到了一个问题，我得到了这样的列表（机场）：
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
有人告诉我这是定向的，并要求找到最短路径。我将它放入我在 Github 上找到的 Dijkstra 算法（这是一个开放式计算机期中考试，所以我们几乎没有足够的时间从头开始编写算法），我的教授说它返回的最短路径不正确而且它甚至不是一条可能的路径，因为该列表应该是定向的。我不确定我是否应该修改算法或列表来进行此更正。结果是它返回的第二条最短路径实际上是有向最短路径，但我仍然想知道问题出在哪里。
两者都适用。原因如下：
无向图与具有双向连接的有向图基本相同（ = 连接节点之间的两个相反方向的连接）。
所以你真的不需要做任何事情来让它适用于无向图。您只需要知道可以通过例如从每个给定节点到达的所有节点。 邻接表.
有向图只意味着连接顶点的边能够以一种方式连接，但不能以另一种方式连接。这意味着一个顶点可以与另一个顶点相邻，但另一个顶点可能不与第一个顶点相邻。
在 Dijkstra 算法的上下文中，图是有向的还是无向的并不重要。 Dijkstra 的算法只是引用一个顶点的相邻顶点。如果将图从有向图更改为无向图，则必须修改此邻接表。
Djikstras 算法通常用于 Positive 加权图。也许您将它与广度优先搜索 (BFS) 算法混淆了，后者本质上是未加权图的 Djikstras。 Djikstras 和 BFS 之间的区别在于，当您处理加权路径时，我们现在必须考虑路径成本调整（权重）以及在当前之后访问哪些节点的决定。
您可以在有向图和无向图中使用 Dijkstra 算法，因为当您有从邻接列表前往的边时，您只需将节点添加到 PriorityQueue 中。例如，如果我的一个节点有一条从 A 到 B 的边，权重为 3，那么如果它是从 B 定向的，我将无法将边添加回 A，而从 A 可以将它添加到 B。
与其他答案一样，请确保不要将它与权重混淆。 Dijkstra算法运行在正加权图上，否则优先级队列就没用了。
在您的示例中，Dijkstra 的算法会起作用，因为该图已加权（正向）并且具有有向边。
错误可能是边以无向图的形式被双重分配。将开头的边解析为对象时应小心，不要重复邻接列表中的边。
是的，Dijkstra 适用于有向图和无向图，但所有边权重都应为 +ve。因为如果任何权重是-ve，那么它可能无法给出正确答案。
它适用于无向图，因为在 Dijkstra 中，我们应该始终看到最小边权重。从它的源顶点
Dijkstra 也适用于循环图。这意味着它可以用于无向图。因为图中的无向边可以简单地假设为双向边。 A 到 B。B 到 A。Dijkstra 的作品。
我一直在尝试 google 这个，但我发现的结果只会让我更加困惑。似乎它可以同时用于两者？如果是这样，默认情况下它是为哪个设计的？需要更改什么才能使其以非默认方式工作（无论是定向还是非定向）？
编辑：作为参考，上学期我遇到了一个问题，我得到了这样的列表（机场）：
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
有人告诉我这是定向的，并要求找到最短路径。我将它放入我在 Github 上找到的 Dijkstra 算法（这是一个开放式计算机期中考试，所以我们几乎没有足够的时间从头开始编写算法），我的教授说它返回的最短路径不正确而且它甚至不是一条可能的路径，因为该列表应该是定向的。我不确定我是否应该修改算法或列表来进行此更正。结果是它返回的第二条最短路径实际上是有向最短路径，但我仍然想知道问题出在哪里。
两者都适用。原因如下：
无向图与具有双向连接的有向图基本相同（ = 连接节点之间的两个相反方向的连接）。
所以你真的不需要做任何事情来让它适用于无向图。您只需要知道可以通过例如从每个给定节点到达的所有节点。 邻接表.
有向图只意味着连接顶点的边能够以一种方式连接，但不能以另一种方式连接。这意味着一个顶点可以与另一个顶点相邻，但另一个顶点可能不与第一个顶点相邻。
在 Dijkstra 算法的上下文中，图是有向的还是无向的并不重要。 Dijkstra 的算法只是引用一个顶点的相邻顶点。如果将图从有向图更改为无向图，则必须修改此邻接表。
Djikstras 算法通常用于 Positive 加权图。也许您将它与广度优先搜索 (BFS) 算法混淆了，后者本质上是未加权图的 Djikstras。 Djikstras 和 BFS 之间的区别在于，当您处理加权路径时，我们现在必须考虑路径成本调整（权重）以及在当前之后访问哪些节点的决定。
您可以在有向图和无向图中使用 Dijkstra 算法，因为当您有从邻接列表前往的边时，您只需将节点添加到 PriorityQueue 中。例如，如果我的一个节点有一条从 A 到 B 的边，权重为 3，那么如果它是从 B 定向的，我将无法将边添加回 A，而从 A 可以将它添加到 B。
与其他答案一样，请确保不要将它与权重混淆。 Dijkstra算法运行在正加权图上，否则优先级队列就没用了。
在您的示例中，Dijkstra 的算法会起作用，因为该图已加权（正向）并且具有有向边。
错误可能是边以无向图的形式被双重分配。将开头的边解析为对象时应小心，不要重复邻接列表中的边。
是的，Dijkstra 适用于有向图和无向图，但所有边权重都应为 +ve。因为如果任何权重是-ve，那么它可能无法给出正确答案。 它适用于无向图，因为在 Dijkstra 中，我们应该始终看到最小边权重。从它的源顶点
Dijkstra 也适用于循环图。这意味着它可以用于无向图。因为图中的无向边可以简单地假设为双向边。 A 到 B。B 到 A。Dijkstra 的作品。