1回答

liuyubobobo

2022-06-16

已采纳

1

可以的。面试也没问题。

不过这种写法是语言相关的。在 Java 中，可以把 int[] 视作一个对象。但是在一些语言中，比如 C++ 中，int[] 不是一个对象，所以类似 vector<int[]> 这样的写法是非法的。

另外，使用 Node 的另外一个优势是：可以存储多种不同的数据，包括将自定义的比较方式包含在内。是更加灵活且通用的。

但不管怎样，核心是：我们需要想办法把多个元素“集合”在一起，不管是使用 int[], Node，pair, tuple，ArrayList，LinkedList，甚至是 Map，等等等等各种方式，都可以让多个信息作为一个整体，扔进 pq 中。

2

首先，Dijkstra 不是一定要重复入队的。使用索引堆可以避免重复入队，进一步优化 Dijkstra 的复杂度。但是因为索引堆属于相对“高级”的数据结构，我在课程中也没有介绍。我在课程中介绍的 Dijkstra 算法已经足够应对所有的面试，甚至是所有的竞赛中的 Dijkstra 的问题了。（竞赛的难点不是这种“小的”优化，关键还是问题的建模。）

其次，非常重要的：在我介绍的这种 Dijkstra 算法中，虽然点会重复入队，但是这个重复和你说的 bfs 的重复不一样。

Dijkstra 的重复入队是有条件的：发现了一个到达当前点的更短的路径，也就是说当前的边可以松弛的时候，才可能重复入队。而由于最多每条边只可能松弛一次，所以入队的元素个数最多就是边数那么多。这就是 Dijkstra 算法中 logE 的来源。（P.S. 在我上面说的使用索引堆优化的 Dijkstra 算法中，这一项变为 logV，因为所有的点不会重复入队。）

但是对于 BFS，由于没有松弛的概念，所以重复入队意味着“遍历到”就入队，那就会出现无限的循环。a 和 b 相邻，从 a 走到 b，b 入队。从队里拿到 b，a 又和 b 相邻，a 又入队，这是一个无穷循环。

继续加油！：）

0

2

liuyubobobo

回复

讲武德的年轻人

明白了。关键还是你所说的 dijkstra 的重复入队，从边的角度看，不是重复，每一条边做松弛，就可能入队，一条边的松弛不可能入队两次，也就是 dijkstra 的点的重复入队，是有条件的，从边的角度看，是不重复的；但是 bfs 的重复，是真正的重复。（你说的标记位置解决了无限循环的问题，因为早晚会标记为 true，但是同一个点还是字不断地“无意义”地重复入队了。）

2022-06-16

共2条回复