一道面试题，想要确定两个路口之间的最短距离，用Dijkstra算法合适吗？为什么？

Question

考研复试中的一道面试题。
想要确定两个路口之间的最短距离，用Dijkstra算法合适吗？为什么？

Answer 1

其实常见的主要就两种方法——Dijkstra算法和Floyd算法
Dijkstra算法和Floyd算法的区别之处：
总结来说就是
1.Dijkstra不能处理负权图，Flyod能处理负权图；
2.Dijkstra处理单源最短路径
而Flyod是处理多源最短路径
3.Dijkstra时间复杂度为O（n^2）
Flyod时间复杂度为O（n^3） 空间复杂度为O（n ^ 2）;
所以题目中如果是单源点正权图，就可以考虑用Dijkstra
如果是任意两个点之间的最短路径或者是负权图，就可以考虑用Floyd；

希望对题主有所帮助，可以的话，帮忙点个采纳！