广度优先搜索(BFS)
用于在无权图中寻找从指定起点到目标的最短路径,无法处理带权值的图,因为是模拟行走过程,只记录经过的步数。无权图的典型代表即x,y坐标网格。
算法思想:
从起点出发模拟行走过程,维护一个边缘队列,循环处理队列中的边缘点,每个循环为一步,从当前队列中的每个边缘点外推新的边缘点,加入边缘队列,同时将该旧边缘点移出队列,标记为已到达。最终到达目标终点时的循环次数也就是最少步数,在无权的前提下也等同于最短路径。
Dijkstra算法
用于处理带权但无负权边的图的最短路径问题。
算法思想:
不断扩张已访问点集合,初始时集合中只有起点,每轮循环将一个未访问点加入集合,这个点应当选取所有未访问点中与“整个已访问集合”最距离近的一个点。每轮循环需要持续更新维护的是每个未访问点与“整个已访问集合”的最短距离,以及此距离是通过集合中那个点到达该未访问结点得到的。每当有未访问点被纳入集合,就可能因为多了这个中转点导致部分未访问点与集合距离的缩短。只有在所有点都被纳入集合后才能决定起点到终点的最短路径。