为了得到nlogn的一个下界,我采用了众所周知的排序算法,并将其转换/适应于dijkstra的单源最短路径问题。
我知道你需要创建一个基于数值的图,dijkstra会按顺序遍历它,其他的有什么帮助,如何计算它?
最佳答案
考虑使用n个外圈节点创建一个star graph(一个具有单个中心节点和一组“外圈”节点的图,其中每个外圈节点都有一条边连接到中心节点)然后,将外环中的每个节点vi通过一条边连接到中心节点,该边的代价是阵列的第i个条目。如果从中心节点开始运行Dijkstra的算法,算法将按距离的升序访问每个外圈节点,对应于按排序顺序列出数组元素。
希望这有帮助!