赞
踩
基础知识:迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
问题描述:在有向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短值。
Dijkstra的算法与Prim的最小生成树算法非常相似。像prim的mst一样,我们生成一个以给定源为根的spt(最短路径树)。我们维护两个集合,一个集合包含最短路径树中包含的顶点,另一个集合包含尚未包含在最短路径树中的顶点。在算法的每一步中,我们都会找到一个顶点,它位于另一个集合中(还没有包含的集合),并且与源的距离最小。
下面是Dijkstra算法中使用的详细步骤,用于查找从单个源顶点到给定图中所有其他顶点的最短路径。
算法步骤:
1)创建一个集sptSet(shortest path tree set,最短路径树集),跟踪最短路径树中包含的顶点,即计算并最终确定与源的最小距离。最初,此集合为空。
2)为给定的图中的所有顶点指定距离值。将所有距离值初始化为无穷大(INFINITE)。将源顶点的距离值指定为0,以便首先拾取它。
3)虽然sptSet不包含所有顶点
….a)选择sptSet中不存在且具有最小距离值的顶点u。
….b&#
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。