算法的具体细节问题
来源：10-13 Dijkstra（迪杰斯特拉）算法
慕尼黑9395599
2020-12-14
跟一楼问的问题一样，老师你的原文意思是，通过节点D计算U集合里所有节点的距离，这个所有二字我有点困惑，如果是所有的话，你应该计算一下A通过B到C的距离，再计算一遍A通过B到E.F.D三个点的距离，从而来更新U集合里面的信息，而老师在这里只计算A通过B到C的距离，我不知道是因为B的下一跳是C而不是DEF的原因，还是因为这样计算一遍没有意义的原因，后面F点纳入到S集合后也是这样，你只计算了A通过节点F到D到E的距离，而没有计算此时仍处于U集合里的C的距离，这让我只能猜测，是否只需要计算初始节点通过新加入到S集合中的D节点到D节点下一跳的距离，而后更新U集合，其他不是D节点的下一跳节点不需要计算
写回答
2回答
-
慕函数9135132
2021-01-05
A通过B到达各个节点，那是不是可以说 A通过B到达任何节点的距离全部都要算一遍？比如ABC，ABCA,ABCD等等，例子中只是通过B计算吓一跳的距离。是不是说网络中是按吓一跳计算 还是按我这里所说的通过B计算各个节点的距离.....012021-01-05 -
咚咚呛
2020-12-14
可以的，对于一些非必要步骤，确实可以精简，但是从算法的角度去看的话，这种优化，既不是O(n)的优化，也不是O(logn)的优化，而只是一些特殊情况的判断条件，所以在描述完整的算法思路时，一般不会优先考虑。希望对你有所帮助。
00
相似问题