2021-11-06 23:10:14 +08:00
|
|
|
|
# 最短路径算法
|
2021-11-06 22:03:15 +08:00
|
|
|
|
|
|
|
|
|
|
|
2021-11-06 23:10:14 +08:00
|
|
|
|
最短路径问题： 寻找图（由结点和路径组成的）中两结点之间的最短路径
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
实现算法
|
|
|
|
|
|
|
|
|
|
|
|
* A* 算法
|
|
|
|
|
|
* Floyd
|
|
|
|
|
|
* Dijkstra(迪杰斯特拉)
|
|
|
|
|
|
* bellman-ford
|
|
|
|
|
|
* spfa
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
## A* 算法
|
|
|
|
|
|
|
|
|
|
|
|
`A*（A-Star)`算法是一种静态路网中求解最短路径最有效的直接搜索方法; 算法中的距离估算值与实际值越接近，最终搜索速度越快。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
## Dijkstra：最短路径算法
|
|
|
|
|
|
|
|
|
|
|
|
Dijkstra 解决图中一点到其余各点到最短路径的问题
|
|
|
|
|
|
|
|
|
|
|
|
Dijkstra是荷兰的计算机科学家,提出”信号量和PV原语“,"解决哲学家就餐问题",”死锁“也是它提出来的）
|
|
|
|
|
|
|
2021-11-06 22:03:15 +08:00
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
