java - 查找节点之间的最短路径以及图是否连通

Question

下面显然是一道作业题。我听不懂教授在说什么，所以我什至不需要知道从哪里开始寻找找到这个问题的答案所需的信息。如果您能给我一些关于在哪里学习这些东西以及如何解决这个问题的线索，我将不胜感激。

在下图中，找到两个节点之间的最短路径 - 您的选择，但让问题变得有趣。

这是一个连通图吗？

Answer 1

最好首先了解图形在内存中的表示方式。如果由您决定，您可以使用二维数组，因为这是表示加权边的最简单方法。

最容易实现的最短路径算法可能是 Djikstra 的算法，它比 A* 稍慢但简单。要使用 Djikastra，您需要首先实现优先级队列。在 Java 中，有一个 PriorityQueue 类，否则您必须自己实现它。之后，使用维基百科或其他任何地方提供的伪代码，实现应该相当简单。