Dijkstra的有向图或无向图的算法？ [英] Is Dijkstra's algorithm for directed or undirected graphs?

问题描述

我一直试图谷歌这一点，但我发现的结果只是增加了我的困惑。它似乎可以用于两者？如果是这样，默认设计的是哪种方式，需要改变什么以使其以非默认方式工作（无论是指向还是不指导）？

编辑：作为参考，上个学期我有一个问题，我得到了这样一个列表（机场）：

  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 $ b $ EGO，KZN，1.2603 
 GYD，NBC，2.0755 
  

我被告知它是有指示的，并要求找到最短路径。我把它放到我在Github上找到的Dijkstra算法（这是一个开放式计算机期中考试，因此我们没有足够的时间从头开始编写算法），我的教授说它返回的最短路径不正确，它是甚至没有可能的路径，因为该列表应该是有针对性的。我不确定是否应该修改算法或列表来进行修正。结果是它返回的第二条最短路径实际上是指向最短路径，但我仍然想知道问题出在哪里。 解决方案

它可以应用于两者。原因如下：

一个无向图图基本上与向下图连接（=相反方向上的两个连接）。

所以你并不需要做任何事情来使它适用于无向图。您只需要知道可以通过例如每个给定节点到达的所有节点。一个邻接列表。

I keep trying to google this, but the results I'm finding are just adding to my confusion. It seems that it can be possibly used for both? If so, which is it designed for by default and what needs to change to make it work the non-default way (whether that be directed or undirected)?

Edit: for reference, I had a problem last semester where I was given a list like this (airports):

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

I was told it was directed, and asked to find the shortest path. I put it into a Dijkstra's algorithm I found on Github (it was an open-computer midterm so we didn't have nearly enough time to write the algorithm from scratch) and my professor said the shortest path it returned was incorrect and that it was not even a possible path because the list was supposed to be directed. I wasn't sure if I was supposed to then modify the algorithm or the list to make this correction. It ended up being the case that the 2nd shortest path it returned was actually the directed shortest path, but I'm still wondering what the problem was.

解决方案

It can be applied to both. Here is why:

An undirected graph is basically the same as a directed graph with bidirectional connections (= two connections in opposite directions) between the connected nodes.

So you don't really have to do anything to make it work for an undirected graph. You only need to know all of the nodes that can be reached from every given node through e.g. an adjacency list.

这篇关于Dijkstra的有向图或无向图的算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！