出处：信息科学卷 • 计算机科学技术 • 软件与系统
| 词条 | 迪克斯彻算法 |
| 释义 | 迪克斯彻算法 迪克斯彻算法 寻找单源最短路径的主要算法。适用于非负权值的加权图。由荷兰计算机科学家迪克斯彻（Edsger Wybe Dijkstra，1930—2002）提出。该算法保存一个顶点集S。S中的顶点是已经找到了最短路径的顶点。开始时，将源点假设在顶点集合S。然后反复执行以下循环，直至顶点集S 包含所有的顶点为止：对于不在S中的每个顶点，考察新加入顶点集S的顶点是否有边到达自己；如果存在，则检查经过该顶点的这条路径是否比原来已知的路径要短；如果是，则更新源点到此顶点的距离和路径；然后，从不在 S的顶点中寻找一个路径最短的顶点加入顶点集S。该算法时间复杂度为O（N 出处：信息科学卷 • 计算机科学技术 • 软件与系统 |
| 随便看 |
百科全书收录258893条中英文百科知识，基本涵盖了大多数领域的百科知识，是一部内容开放、自由的电子版百科全书。