|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用算法 > 常用算法 > 图的相关算法 >
|
|
相关知识点：7个
|
|
|
|
|
所谓单源点最短路径，是指给定带权有向图G和源点ν0，求从ν0到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了按路径长度递增的次序产生最短路径的算法，其思想是：把网中所有的顶点分成两个集合S和T，S集合的初态只包含顶点ν0，T集合的初态包含除ν0之外的所有顶点，凡以ν0为源点，已经确定了最短路径的终点并入S集合中，按各顶点与ν0间最短路径长度递增的次序，逐个把T集合中的顶点加入到S集合中去。
|
|
|
|
每次从T集合选出一个顶点u并使之并入集合S后（即ν0至u的最短路径已找出），从ν0到T集合中各顶点的路径有可能变得更短。例如，对于T集合中的某一个顶点νi来说，其已知的最短路径可能变为（ν0，…，u，νi），其中的…仅包含S中的顶点。对T集合中各顶点的路径进行考查并进行必要的修改后，再从中挑选出一个路径长度最小的顶点，从T集合中删除它，同时将其并入S集合。重复该过程，就能求出源点到其余各顶点的最短路径及路径长度。
|
|
|
|
在下图所示的有向网中，用迪杰斯特拉算法求解顶点V0到达其余顶点的最短路径的过程如下表所示。
|
|
|
|
|
|
|
|
|
|
迪杰斯特拉算法求解上图（a）顶点V0到V1、V2、V3、V4、V5最短路径的过程
|
|
|
