最短路径算法(Shortest-path Algorithms)

时间:2023-02-03 09:34:58

0) 引论

正如名字所言,最短路径算法就是为了找到一个图中,某一个点到其他点的最短路径或者是距离。

最短路径算法一般分为四种情况:

a) 无权重的最短路径

b) 有权重的最短路径

c) 边的权重为负的图

d) 无圈的图

ps:上面的情况针对的都是有向图。


1) 无权重的最短路径

下图是一个例子:假设我们取点v3作为初始点,计算点v3到图中所有点的路径以及距离(包括点v3)。

a) v3到v3的路径长为0。

b) 沿着v3的邻接点查找,找到v1,那么v3到v1的路径长为1;找到v6,那么v3到v6的路径长为1。

c) v3的邻接点已经找完了,接下来找v1,v6的邻接点。

d) v1的邻接点为v2,v4,它们对应的路经长为2;v6无邻接点,v6部分结束。

e) v2的邻接点为v4,v5,而v4已经查找过了,舍弃;v2到v5的路径长为3;v4的邻接点为v5,v7,而v5已经查找过了,舍弃;v4到v7的路径长为3。

f) 至此,结束。

最短路径算法(Shortest-path Algorithms)


对于这一步骤,可以用一个表格来表示,以便于编程理解:

表中有3个表示状态的变量:

a) dv表示点s到图中每个点的距离,结合上面的例子,s=v3.

b) pv表示图中点的路径前继点。

c) Known表示点是否被处理,处理了,则标记为1 。

最短路径算法(Shortest-path Algorithms)

伪代码:

void Unweighted(Table T)
{
	int CurrDist;
	Vertex V,W;
	for(CurrDist=0;CurrDist<NumVertex;CurrDist++)
	{
		for each vertex V
			if(!T[V].Known&&T[V].Dist==CurrDist)
			{
				T[V].Known = True;
				for each W adjacent to V
					if(T[W].Dist == Infinity)
					{
						T[W].Dist = CurrDist+1;
						T[W].Path = V;
					}
			}
	}
}


通拓扑排序一样,对于上面的程序也是存在改进的地方的(第07行),我们没有必要去对each vertex V做一下这么多的步骤,只需要对相邻接的点做就好了。因此用一个队列来使每一个处理的点入队,然后处理其邻接的点。

void Unweighted(Table T)
{
	Queue Q;
	Vertex V,W;

	Q = CreateQueue(NumVertex);
	MakeEmpty(Q);
	Enqueue(S,Q);//S is the start Vertex

	while(!IsEmpty(Q))
	{
		V = Dequeue(Q);
		T[V].Known=True;
		for each W adjacent to V
			if(T[W].Dist == Infinity)
			{
				T[W].Dist = T[V].Dist+1;
				T[W].Path = V;
				Enqueue(W,Q);
			}
	}
	Free(Q);
}


2) 有权重的最短路径

有权重的最短路径算法,称之为Dijkstra‘s algorithm。相对于无权重的最短路径算法,有权重的最短路径算法会显得难一点,这是因为权重的引入会使某些路径的加权重长度发生颠倒。

Dijkstra‘s algorithm是一种greedy algorithm。贪婪算法就是在算法的每一个阶段都取最大值。一般情况下,贪婪算法能取得较好的效果。但是贪婪算法是有其缺陷的,也就是说能达到局部最优,而未必能达到全局最优,举个例子,假设要兑换15分的硬币,而硬币有12分的,10分的,5分的,1分的,那么根据贪婪算法,最终的兑换结果为1个12分的,3个一分的;而最优结果应该是一个10分的,一个5分的。(这里我们定义最优为硬币个数最少)。

Dijkstra‘s algorithm的步骤是:

对于每一个阶段,Dijkstra‘s algorithm会在所有未处理的点中选取一个最小距离的点v,然后把给定点s到v的路径定义为最小路径。


下面是一个例子:

最短路径算法(Shortest-path Algorithms)

对应的表的形式表示:

最短路径算法(Shortest-path Algorithms)最短路径算法(Shortest-path Algorithms)最短路径算法(Shortest-path Algorithms)

下面是具体的实现说明:

a) 最初的点s=v1;计算s到图中所有点的最短路径。

b) 找到v1邻接的点v2,v4,分别标出s到v2,v4的路径长,同时对v1标注T[v1].Known=1。

c) 由于v4路径长较小,因此选择v4,找到v4邻接的点v3,v5,v6,v7,标注出他们的路径长;同时对v1标注T[v4].Known=1。

d) 现有的所有未处理路径中v2最短,因此处理v2,找到v2邻接的点v4,v5; v2到v4,v5的路径长远大于v4,v5已有的路径长,因此不更新。同时T[v2].Known=1。

e) 现有的所有未处理路径中v3,v5最短,处理v3,邻接点为v1,v6,路径分别为7,8;对于v3到v6的距离,因为8<9,因此需要更新;对于v3到v1的距离不需要更新。同时T[v3].Known=1。

f)  对于v5,邻接点为v7,v5到v7的路径长为 3+6>5,因此不更新;同时T[v5].Known=1。

g) 现在处理v7,v7的邻接点为v6,v7到v6的路径长为5+1<8,因此需要更新;同时T[v7].Known=1。

h) 现在处理v6,v6没有邻接点了,因此可以结束了。同时T[v6].Known=1。


伪代码实现:

typedef int Vertex;
typedef int DistType;

struct TableEntry
{
	List Header;
	int Known;
	DistType Dist;
	Vertex Path;
}

#define NotAVertex (-1)
typedef struct TableEntry Table[NumVertex];

void InitTable(Vertex Start,Graph G,Table T)
{
	int i;
	ReadGraph(G,T);
	for(i=0;i<NumVertex;i++)
	{
		T[i].Known = 0;
		T[i].Dist = Infinity;
		T[i].Path = NotAVertex;
	}
	T[Start].Dist = 0;
}

void Dijkstra(Table T)
{
	Vertex V,W;
	for(;;)
	{
		V = FindSmallestUnknownDistanceVertex();
		if(V==NotAVertex)
			break;
		T[V].Known = Ture;
		for each W adjacent to V
			if(!T[V].Known)
				if(T[V].Dist+Cvw<T[W].Dist)
				{
					Decrease(T[W].Dist to T[V].Dist+Cvw);
					T[W].Path = V;
				}
	}
}
相对于无权重的最短路径,这里权重的更新为Dist = Dist + Cvw;


3) 边的权重为负的图

边的权重为负,这将是一个比较糟糕的事情,这无法利用上面的两种方法处理,因为只要循环负边,则路径可以无限变小,如下图所示:

最短路径算法(Shortest-path Algorithms)

点1到点6的最短路径是2么?当然不是,我们没法求出其最短路径,因为我们可以沿着路径1,6,5,7,6这样一次下来,路径为-3,由于6,5,7,6是一个圈,我们可以一直循环下去且路径为负值,因此无法确定点1到点6的最短路径。

那么遇到这种问题该怎么解决呢?

a) 给所有权重加上一个正值,是所有权重均为非负,上面的例子中,所有权重加上11,则就可以应用Dijkstra方法处理了。


4) 无圈的图

对于无圈图,也可以应用Dijkstra方法处理,无圈图也可以看做是上面的一种特例。对于无圈图,可以利用拓扑排序的顺序选择起始点,权重的更新也可以按照拓扑排序的顺序进行,因此算法可以一次进行,这个可以看做是对Dijkstra方法的改进,并且是向简单方向的改进。

无圈图可以模拟像下坡滑雪等问题,一直需要沿着向下的方向,不应该有圈。

而无圈图的最大应用不在这里,而是一个被称之为关键路径分析法的应用。

如下图所示:

最短路径算法(Shortest-path Algorithms)

这幅图表示的意思是要想做D中的事情,必须先做完A和B,而A,B则是可以并行的。因此这个图中的问题不是寻找最短路径,而是找到并行完成图中的所有点所需要的最短时间,以及最晚的时间。

解决这个问题需要把上面的动作节点图转换为下面的事件节点图

最短路径算法(Shortest-path Algorithms)

对于事件节点图,只需要找出第一个事件到最后一个事件的最长路径的长就好了。

假设ECi表示节点i的最早完成时间,那么利用下面的法则

最短路径算法(Shortest-path Algorithms)

最早完成时间结果为:

最短路径算法(Shortest-path Algorithms)