Question

数据结构 图之单源最短路径

Answer 1

百度百科

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。

问题描述

给定一个带权有向图 G=(V,E)。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

即先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

举个书上的题当作例子

初始化的距离向量

这时候的路径向量为：

接下来，就是将源点A到其他结点距离最短的结点找出来，这里最短的是到D结点加到集合S当中,并且：

距离向量变为：

由于现在A到G和F通过了D顶点，导致顶点G和F的前驱结点变为了D，即路径向量变为3

路径向量为：

接下来继续向后找，发现最短的路径是到E,所以将其加入集合S，并且：

距离向量变为：

由于 A->C 变成了 A->E->C ,所以C的前驱结点变为了E，即4

路径向量为：

继续向下推导，最终结果为：

距离向量：

路径向量：

可以从表中的数据得出：

总结为：