Dijkstra 算法的基本思路

假设每个点都有一对标号(dj ,pj ) , 其中dj是从起源点s到点j的最短路径的长度(从顶点到其本身的最短路径是零路
(没有弧的路) , 其长度等于零) ; pj 则是从s到j 的最短路径中j 点的前一点。

求解从起源点s 到点j 的最短路径算法的基本过程如下:

1) 初始化。

起源点设置为:
① ds=0, ps为空;
② 所有其他点: di=∞, pi=?;
③ 标记起源点s,记k=s, 其他所有点设为未标记的。

2) 检验从所有已标记的点k 到其直接连接的未标记的点j 的距离, 并设置:

dj = min[dj ,dk +lkj]式中, lkj是从点kj 的直接连接距离。

3) 选取下一个点。

从所有未标记的结点中,选取dj中最小的一个i:di = min [dj ,所有未标记的点j ]点i 就被选为最短路径中的一点, 并设为已标记的。

4) 找到点i 的前一点。

从已标记的点中找到直接连接到点i 的点j *, 作为前一点, 设置:i = j *

5) 标记点i

如果所有点已标记, 则算法完全推出, 否则, 记k= i, 转到2) 再继续。



关于 McKelvin

a hacker who's interested in `music computing` and `network security`.
此条目发表在 Work 分类目录。将固定链接加入收藏夹。