最短路径问题在实际生活中的应用(3)
时间:2017-03-27 20:53 来源:毕业论文 作者:毕业论文 点击:次
2.1 Dijkstra算法 Dijkstra(迪杰斯特拉)算法又称为标号法，是1959年荷兰计算机科学家E.W.Dijkstra提出的关于最短路径的搜索算法，该算法是很具有代表性的单源最短路径的实用算法[2]，主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止，用于计算一个节点到其他所有节点的最短路径，表述方法通常有两种，一种是临时标号方式和永久标号方式，另外一种是open和close的方式，通常采用前一种方式，原始的Dijkstra算法将网络结点分为未标记结点、临时标记结点和永久标记结点这三个部分[13]。在网络中的所有结点首先都要进行初始化为未标记节点，然后在搜索过程中将与最短路径中结点相通的结点标为临时标记结点，每次循环都是从临时标记结点中搜索距离源点路径长度最短的结点作为永久标记结点，直到所有的目标结点成为永久标记结点才结束算法。该算法是目前多数系统解决最短路径问题的理论基础，程序设计简单通用性比较强，但是该算法遍历计算的节点比较多，因此效率比较低。 2.1.1 算法思想 Dijkstra算法，是迪杰斯特拉采用贪心法算法的策略提出的按照路径长度递增的顺序产生的最短路径的算法[5]，该算法的算法思想是，设置两个集合 和 ，集合 存放已经找到最短路径的顶点的集合，集合 存放当前还未找到的最短路径的顶点，初始状态 中存放 然后不断从 中不断的找出到定 点的最短路径，把这个定点加入到 中，集合 中每加入一个顶点，都要修改定点 到集合 中剩余其他定点的值，直到经过 步，集合 为空，就可以得到从起点到其他各节点的最短路径。 Dijkstra算法是从起点出发，逐步向外探寻最短路径。 2.1.2 算法描述 1)假设起始点 ， 中只包含顶点 ，除去 ，剩余顶点均在集合 中，可以得出到 对应的距离为 ，即 。我们规定 中顶点对应的距离值：如果图中有弧,用 表示，并且 顶点的距离为该弧的权值，否则就为 。 2)从 中选择一个其距离值最小的顶点 ，然后加入到 中。 3)每往 中加入一个顶点 后，就要对 中各个顶点的距离值进行一次修改。如果 做中间顶点，使得 的值小于 值，则用 代替原来 的距离值。 (责任编辑：qin) |