迪杰斯特拉算法求最短路径的描述
时间: 2023-11-28 11:44:41 浏览: 36
迪杰斯特拉算法是一种用于解决带权有向图或者无向图的单源最短路径问题的算法。该算法的基本思想是:维护一个集合S,表示已经求出最短路径的顶点集合,初始时S中只包含源点;然后不断从剩余的顶点中选择一个距离源点最近的顶点加入到S中,并更新其它顶点到源点的距离。具体实现时,可以使用一个数组dist来记录每个顶点到源点的距离,使用一个数组visited来记录每个顶点是否已经加入到S中,使用一个二维数组graph来表示图中各个顶点之间的边权。
迪杰斯特拉算法的具体步骤如下:
1. 初始化:将源点加入到集合S中,dist数组中将源点的距离设为0,visited数组中将源点标记为已访问。
2. 从剩余的顶点中选择一个距离源点最近的顶点u,并将其加入到集合S中。
3. 对于所有从u出发的边,更新其它顶点到源点的距离。具体地,对于每个与u相邻的顶点v,如果v未被访问过且从源点到v的距离比当前记录的距离更短,则更新dist[v]的值为dist[u]+graph[u][v]。
4. 重复步骤2和步骤3,直到所有顶点都被加入到集合S中。
最终,dist数组中记录的就是源点到各个顶点的最短距离。