algorithm - Dijkstra 算法是用于有向图还是无向图？

Question

我一直试图用谷歌搜索这个，但我发现的结果只会让我更加困惑。似乎它可以同时用于两者？如果是这样，默认情况下它是为哪个设计的？需要更改什么才能使其以非默认方式工作(无论是定向还是非定向)？

编辑:作为引用，上学期我遇到了一个问题，我得到了这样的列表(机场):

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 算法中(这是一个开放式计算机期中考试，所以我们几乎没有足够的时间从头开始编写算法)，我的教授说它返回的最短路径是不正确的，它是甚至没有可能的路径，因为该列表应该是定向的。我不确定我是否应该修改算法或列表来进行此更正。结果是它返回的第二条最短路径实际上是有向最短路径，但我仍然想知道问题出在哪里。

Answer 1

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

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

因此，您实际上无需执行任何操作即可使其适用于无向图。您只需要知道可以通过例如从每个给定节点到达的所有节点。一个邻接表。