【算法百题之四十六】20分钟回顾四大寻路算法
【算法百题之四十六】20分钟回顾四大寻路算法
大家好，我是Lampard~~
很高兴又能和大家见面了，接下来准备系列更新的是算法题，一日一练，早日升仙！
今天主要是总结归纳下之前写过的四大寻路算法
简而言之，对于寻找单个结点到单个结点之间的路径时，我们可以使用A*寻路算法。若是找单个节点到其余结点的所有最短路径已经其长度的话，可以使用迪杰斯特拉算法和SPFA贝德曼算法。其中迪杰斯特拉算法的时空复杂度都更优，可是其不能存在负权值的边（因为其没找到一个结点就算算出其最短路径且不会再更新），所以存在负权值的情况下可以考虑贝德曼算法（贝德曼算法不能存在负权环，需要注意防止死循环）。对于想求出每个结点两两之间的最短路径，则可以使用弗洛伊德算法，算法简单也可以解决负权边。
