迪杰斯特拉算法

用手机看条目

出自 MBA智库百科(https://wiki.mbalib.com/)

(重定向自Dijkstra)

迪杰斯特拉算法(Dijkstra)

目录

什么是迪杰斯特拉算法

  迪杰斯特拉算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

迪杰斯特拉算法的思想

  按路径长度递增次序产生算法:

  把顶点集合V分成两组:

  (1)S:已求出的顶点的集合(初始时只含有源点V0)

  (2)V-S=T:尚未确定的顶点集合

  将T中顶点按递增的次序加入到S中,保证

  (1)从源点V0到S中其他各顶点的长度都不大于从V0到T中任何顶点的最短路径长度

  (2)每个顶点对应一个距离值

  S中顶点:从V0到此顶点的长度

  T中顶点:从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

  依据:可以证明V0到T中顶点Vk的,或是从V0到Vk的直接路径的权值;或是从V0经S中顶点到Vk的路径权值之和

  (反证法可证)

  求最短路径步骤

  算法步骤如下:

  G={V,E}

  1. 初始时令 S={V0},T=V-S={其余顶点},T中顶点对应的距离值

  若存在<V0,Vi>,d(V0,Vi)为<V0,Vi>弧上的权值

  若不存在<V0,Vi>,d(V0,Vi)为∞

  2. 从T中选取一个与S中顶点有关联边且权值最小的顶点W,加入到S中。

  3. 对其余T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的距离值缩短,则修改此距离值。

  重复上述步骤2、3,直到S中包含所有顶点,即W=Vi为止。

  Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构图论运筹学等等。

相关条目

本条目对我有帮助1
MBA智库APP

扫一扫,下载MBA智库APP

分享到:
  如果您认为本条目还有待完善,需要补充新内容或修改错误内容,请编辑条目

本条目由以下用户参与贡献

LuyinT.

评论(共0条)

提示:评论内容为网友针对条目"迪杰斯特拉算法"展开的讨论,与本站观点立场无关。

发表评论请文明上网,理性发言并遵守有关规定。

打开APP

以上内容根据网友推荐自动排序生成

闽公网安备 35020302032707号