迪克斯彻算法是寻找单源最短路径的主要算法。

应用

适用于非负权值的加权图。

历史

由荷兰计算机科学家迪克斯彻（Edsger Wybe Dijkstra，1930-2002）提出。

例证

该算法保存一个顶点集S。S中的顶点是已经找到了最短路径的顶点。开始时，将源点假设在顶点集合S。然后反复执行以下循环，直至顶点集S包含所有的顶点为止：对于不在S中的每个顶点，考察新加入顶点集S的顶点是否有边到达自己；如果存在，则检查经过该顶点的这条路径是否比原来已知的路径要短；如果是，则更新源点到此顶点的距离和路径；然后，从不在S的顶点中寻找一个路径最短的顶点加入顶点集S。该算法时间复杂度为O（N2）。1

本词条内容贡献者为:

苏智勇 - 副教授 - 南京理工大学自动化学院

迪克斯彻算法

图文简介

迪克斯彻算法是寻找单源最短路径的主要算法。