dijkstra算法是基于图的广度优先搜索方式吗？

Question

老师，网上还有种dijkstra算法是基于图的广度优先搜索方式，相当于二叉树的层序遍历，与你讲的这种方式不一样，你这节课讲的并不是广度优先搜索的方式，因为倒数第二步加入的是E不是C。
请问这2种都是dijkstra算法吗？

Answer 1

咚咚呛 2019-08-26 00:23:41

嗯，按照你的描述，如果使用层序遍历的话，应该先加入C再加入E的，因为从AC是相邻的，AE是相隔的。

但是不管是哪种，都是Dijkstra算法。

因为Dijkstra算法的核心不在于遍历的方式，而是在于对集合的操作，可以看到不管是先C后E还是先E后C，Dijkstra算法都是定义了两个集合的距离，并且通过搜索最短距离和操作集合的元素，完成了对路径的搜索，二叉树遍历可以理解为是遍历实现的一种方式。