图算法 单源最短路径问题 无权最短路径

时间:2020-12-13 11:42:24

单源最短路径问题

给定一个赋权图 G = (V, E)和一个特定顶点s作为输入,找到s到G中每一个其他顶点的最短赋权路径。

无权最短路径(解法可被用来做广度优先遍历

图算法 单源最短路径问题 无权最短路径

一个无权图G。使用某个顶点s作为输入参数,要找出从s到所有其他顶点的最短路径。

这里给出一个O( | E | + | V | )的解法。O( | V | ^2)的解法不做讨论。

对于每个顶点,跟踪三条信息,顶点是否被处理(未处理为F,处理过为T,初始为F),s到此顶点的路径长dv(s初始为0,其他为INFINITY),此顶点之前顶点

在任意时刻,只存在两种类型的dv不是INFINITY的Unknown顶点,一些顶点的dv=currDist,另一些dv=currDist+1。 一种抽象是保留两个盒子,1号盒子装有dv = currDist的那些未知顶点,而2号盒子装有dv = currDist +1的那些顶点。找出一个合适顶点的测试可以用查找1号盒内的任意顶点v代替。在更新v的临界顶点w后,将w放入2号盒中。

可以使用一个队列进一步简化上述模型。迭代开始时,队列只含有距离为currDist的顶点。当添加距离为currDist+1的那些邻接顶点时,由于它们自队尾入队,因此保证它们直到所有距离为currDist的顶点都被处理之后才处理。

//无权最短路径问题的伪代码
void unweighted( Vertex s ){
//一个队列
Queue<Vertex> q = new Queue<Vertex>( );
//每个顶点初始距离为INFINITY
for each Vertex v
v.dist = INFINITY;
//s初始距离为0
s.dist = 0;
q.enqueue( s );

while( !q.isEmpty( ) ){
Vertex v = q.dequeue( );
//遍历v的邻接顶点
for each Vertex w adjacent to v
//如果dist是INFINITY说明没有处理过
if( w.dist == INFINITY ){
w.dist = v.dist + 1;
w.path = v;
q.enqueue( w );
}
}
}
下图演示算法运行(该图还包括是否known的变化,代码中是不需要的)

以v3为开始顶点

图算法 单源最短路径问题 无权最短路径