最短路径和Dijkstra算法

Question

我似乎无法在互联网上找到任何关于这个问题的迹象，因为我正在考试，所以我 运行 没时间了，这个问题很简单，欢迎任何解释（虽然一个简单的是或否也一样）。

对于Dijkstra算法，图一定是强连通的吗？也就是说每个顶点都可以从任何其他顶点到达？或者是否可能有无法到达的顶点，因此您必须使用该算法从另一个节点开始？

补充一下这个问题：Dijkstra 算法是否只适用于无向图？因为我教科书中的所有示例都与无向边有关。

Answer 1

无向图基本上只是一个有向图，但具有双向连接。所以不，Dijkstra 的 可以 也适用于有向图。

对于弱连通图，视情况而定。

假设您有图 A 部分和图 B 部分。您可以从 A 进入 B，但不能从 B 进入 A。如果您从 A 开始并想找到进入 B 的最短路径，Dijkstra 就可以了。但是自然地，您不能从 B 开始并尝试找到到 A 节点的路径。