7.5　最短路径

在许多应用领域,带权图常用于描述某个网络,如通信网络、交通网络。这时,各边的权值表示两点之间通信的成本或交通费用。在该应用中经常要解决的一类问题就是:在任意指定的两点之间建立通路,最小的代价是多少。这类问题实际上就是求带权图中两点之间最短路径的问题。在带权图中,两个顶点之间的路径长度定义为两顶点间路径上各边的权值之和。路径的开始顶点称为源点,目的顶点称为终点。所谓图的最短路径问题就是求从源点到终点之间具有最短路径长度的那条路径。如果从图中某一顶点（源点）到达另一顶点（终点）的路径可能不止一条,那么就需要找到一条使得沿此路径上各边上的权值总和达到最小的路径。

7.5.1　单源最短路径

单源最短路径问题是指在有向网G＝（V,R）中,找出从某个顶点s（s∈V）,使其到V中其余各顶点的最短路径。如图7－32所示的有向网中顶点v₀到其他顶点的单源最短路径如下。

图7－32　有向网

（1）v₀到v₁的最短路径为:（v₀,v₁）,长度为10。

（2）v₀到v₂的最短路径为:（v₀,v₃,v₂）,长度为50。

（3）v₀到v₃的最短路径为:（v₀,v₃）,长度为30。

（4）v₀到v₄的最短路径为:（v₀,v₃,v₂,v₄）,长度为60。

对于给定的有向网G＝（V,R）和源点v,可以用Dijkstra算法求单源最短路径。

1.Dijkstra算法思想

Dijkstra算法认为最短路径的子路径也是最短路径。若已知路径（v₀v₁v₂v₃…v_n－1v_n）是从v₀到v_n的最短路径,则途径中的某顶点v_i也为从v₀到v_i最短路径。因此,该算法按路径长度的递增次序,逐步产生源点到各顶点之间的最短路径。首先,求出长度最短的一条最短路径,再参照它求出长度次短的一条最短路径,依此类推,直到从顶点v到其他各顶点的最短路径全部求出为止。

2.Dijkstra算法步骤

（1）将图的顶点集合V分为两个集合S和V－S,其中S是最短路径已经确定的顶点集合,初值为S＝{v₀},v₀为源点。V－S是最短路径尚未确定的顶点集合。为了区分S集合和V－S集合,定义visited数组,长度为图中顶点数,其元素用于区分是否已经找到源点到该顶点的最短路径,初始值均为false。设数组distance记录从源点到其余各结点当前的最短路径,初始为distance[i]＝（v₀,v_i）的权值i＝2,3,…,n。设数组prev来记录从源点到其余顶点最短路径上最后经过的顶点,这样就可以推导出最短路径,初始为pre[v]＝0（源点）,v≠0。

（2）从S之外即V－S中选取一个顶点w,使distance[w]最小（即distance[w]＝min{distance[i]｜i∈V－S}）,并把w加入集合S,即visited[w]＝true。

（3）调整distance中记录的从源点到V－S中每个顶点的最短距离,判断加进w做中间顶点,是否使得v的最短特殊路径长度变短。如果distance[w]＋（v,w）的权值＜distance[v],则distance[v]＝distance[w]＋（v,w）的权值,并且修改pre[v]＝w,否则不做更改。

（4）重复上述过程,直到S中包含V的所有顶点为止,即visited数组元素均为true。数组distance就记录了从源点到图中各顶点的最短路径长度（数组pre可推导最短路径）。

表7－4中记录了对图7－32所示的有向网执行Dijkstra算法的过程。

表7－4　Dijkstra算法

下面伪代码实现了求v₀到图中其他顶点的最短路径及长度。

下面用C语言实现Dijkstra算法的代码。

分析算法代码可知,Dijkstra算法的时间复杂度是O（n²）。

7.5.2　每一对顶点之间的最短路径

找出带权图中任意顶点v_i和v_j之间的最短路径,称为求带权图的每一对顶点对之间的最短路径。可以每次以一个顶点为源点,重复执行Dijkstra算法n次,这样就可以求得所有的顶点对之间的最短路径及其最短路径长度,其时间复杂度为O（n³）。此外,还有一种更直接的方法求得每对顶点间的最短路径,即弗洛伊德（Floyd）算法。具体思想是每一次将一个节点作为中间节点,看看从源点到中间顶点,再从中间顶点到终点的距离是不是比已知的源点到终点的距离短,如果短的话则替代原有路径。

下面求顶点v_i到顶点v_j的最短路径。如果从v_i到v_j存在一条路径（v_i,v_j）,但该路径不一定是最短路径,则需要进行n次试探。首先考虑加入中间顶点v₀,检查路径（v_i,v₀,v_j）是否存在。如果存在,则比较（v_i,v_j）和（v_i,v₀,v_j）的路径长度,取长度较短者为从v_i到v_j的最短路径。再增加一个顶点v₁,继续进行试探。假设在路径上再增加一个顶点v_k,而（v_i,…,v_k）和（v_k,…,v_j）分别是从v_i到v_k和从v_k到v_j的最短路径,则将（v_i,…,v_k,…,v_j）和已经得到的从v_i到v_j的最短路径相比较,其长度较短者便是从v_i到v_j新的最短路径。有时加入中间顶点后的路径比原路径长,则保持原路径不变。将所有顶点作为中间顶点插入后,就可以确定v_i和v_j之间的最短路径了。为了求出所有顶点对之间的最短路径,可以每加入一个中间顶点后,查看所有顶点对之间是否有新的最短路径出现。

如图7－33所示的过程是按照弗洛伊德（Floyd）算法对图中的有向网求解顶点间最短路径的步骤。其中,dist记录目前求出的顶点间的最短路径长度,path记录顶点间的最短路径。

图7－33　弗洛伊德（Floyd）算法原理

续图7－33

如图7－34所示,定义一个n行n列的二维数组D实现上图中的dist。初始时,其值为网的邻接矩阵的值,即D[i][j]＝edges[i][j]。加入n的顶点作为中间顶点,就是对数组D进行n次迭代,在进行第k次迭代时,使用如下的公式。

D^k[i][j]＝min{D^k－1[i][j],D^k－1[i][k]＋D^k－1[k][j]}

在第k次迭代时,针对顶点k进行。原D^k－1矩阵的第k行、第k列保持不变,对角线元素也不变。

Floyd算法在求最短路径过程中还需要保存路径的组成。路径信息的保存可定义一个n行n列的二维数组P,P[i][j]的值表示从i到j的最短路径上j的前一结点的序号。

图7－34　弗洛伊德（Floyd）算法的实现

Floyd算法的C语言实现如下。

由代码分析可知,Floyd算法的时间复杂度为O（n³）,其重复执行n次的Dijkstra算法的时间复杂度一样,但算法更直接。