算法——单源最短路径：Bellman-Ford算法、Dijkstra算法

超、凢脫俗 2022-08-12 00:11 143阅读 0赞

## 前言 ##

在最短路径问题中，约定图[![G=(E,V)][G_E_V]][G_E_V_G_E_V]是一个带权值的有向图。最短路径是解决两节点之间的最小代价问题。最短路径有几种分类：单源最短路径；单目标最短路径；单节点对最短路径；所有节点对最短路径。下面记录单源最短路径问题。

## 单源最短路径 ##

### 定义： ###

单源最短路径是给定一个图[![G=(E,V)][G_E_V]][G_E_V_G_E_V]，希望从一个源节点[![s\\epsilon V][s_epsilon V]][s_epsilon V_s_epsilon V]到每个节点[![v\\epsilon V][v_epsilon V]][v_epsilon V_v_epsilon V]的最短路径。

### 单源最短路径的算法 ###

在介绍算法之前，首先必须介绍下松弛操作，在整个算法中，松弛操作是很重要的，松弛操作的目的是要获得最短路径估计[![v.d][]][v.d 1]；在任何操作之前必须对节点进行初始化操作，松弛过程：将节点[![s][]][s 1]到节点[![u][]][u 1]之间的最短路径距离加上节点[![u][]][u 1]到节点[![v][]][v 1]之间的边权值，并与当前节点[![s][]][s 1]到节点[![v][]][v 1]的最短路径估计进行比较，如果前者较小，则更新最短路径估计[![v.d][]][v.d 1]和前驱[![v.front][]][v.front 1]属性。

//初始化操作
    INITIALIZE-SINGLE-SOURCE(G,s)
    	for each vertex v ∈ G.V 	
    		v.d = inf				
    		v.front = NIL			
    	s.d = 0

//松弛操作
    RELAX(u,v,w) //w是权值函数
    	if v.d > u.d + w(u,v)
    		v.d = u.d + w(u,v)
    		v.front = u

松弛操作过程结构：

![SouthEast][]

根据对图的边进行不同松弛次数和次序，解决单源最短路径问题，下面介绍两种算法：Bellman-Ford算法和Dijkstra算法。

#### Bellman-Ford算法 ####

该算法适用于边权值可为负，但不能有权值为负带有环路的图（ 因为如果包含环路，且环路的权值和为正的，那么去掉这个环路，可以得到更短的路径；如果环路的权值是负的，那么肯定没有解） 。该算法是对每一条边进行[![|V|-1][V_-1]][V_-1_V_-1]次松弛，通过对边的松弛操作渐近地降低从源节点[![s][]][s 1]到每个节点[![v][]][v 1]的最短路径估计值[![v.d][]][v.d 1]，直到该估计值与实际的最短路径权重[![\\sigma (s,v)][sigma _s_v]][sigma _s_v_sigma _s_v]相同为止。若该算法的输入图不包含可以从源节点到达的权重为负值的环路，则返回TRUE。

步骤：

1.  初始化图的每个节点；
2.  对每条边进行[![|V|-1][V_-1]][V_-1_V_-1]次松弛操作；
3.  判断最短路径估计值是否与实际权重相同，若相同则返回TRUE，否则返回FALSE；

//Bellman-Ford算法
    BELLMAN-FORD(G,w,s)
    	INITIALIZE-SINGLE-SOURCE(G,s)
    	for i = 1 to |G.V|-1
    		for each edge (u,v) ∈ G.E 	
    			RELAX(u,v,w)
    	for each edge (u,v) ∈ G.E 
    		if v.d > u.d + w(u,v)
    			return FALSE
    	return TRUE

procedure BellmanFord(list vertices, list edges, vertex source)
 // 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息
 
 // 步骤1：初始化图
 for each vertex v in vertices:
 if v is source then distance[v] := 0
 else distance[v] := infinity
 predecessor[v] := null
 
 // 步骤2：重复对每一条边进行松弛操作
 for i from 1 to size(vertices)-1:
 for each edge (u, v) with weight w in edges:
 if distance[u] + w < distance[v]:
 distance[v] := distance[u] + w
 predecessor[v] := u
 
 // 步骤3：检查负权环
 for each edge (u, v) with weight w in edges:
 if distance[u] + w < distance[v]:
 error "图包含了负权环"

举例：算法执行过程中，源节点为 [![s][]][s 1]，图a是初始化后的结果。每一次松弛操作对边的处理次序都是：

[![(t,x),(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t),(s,y)][t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y]][t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y_t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y]，操作的时候记住要按照顺序进行松弛，例如从图a到图b最短路径估计值的变化过程是：第二行：表示初始化结果；第三行：表示按顺序执行完[![(t,x),(t,y),(t,z),(x,t),(y,x),(y,z),(z,x),(z,s),(s,t)][t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t]][t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t]后的结果；第四行：表示执行完[![(s,y)][s_y]][s_y_s_y]的结果；

![SouthEast 1][]

#### Dijkstra算法 ####

Dijkstra 算法要求所有边的权重都为非负。该算法在执行的过程中维持的关键信息是一组节点集合[![S][]][S 1]，从源节点[![s][]][s 1]到该集合[![S][]][S 1]的每个节点之间都是最短路径已被找到。算法重复从节点集合[![V-S][]][V-S 1]中选择最短路径估计最小的节点[![u][]][u 1]，将节点[![u][]][u 1]加入到集合[![S][]][S 1]，然后对从节点[![u][]][u 1]发出的边进行松弛。

//Dijkstra算法
    Dijkstra(G,w,s)
    	INITIALIZE-SINGLE-SOURCE(G,s)
    	S = ∅
    	Q = G.V
    	while Q ≠ ∅
    		u = EXTRACT-MIN(Q)
    		S = S ∪{u}
    		for each vertex v∈G.Adj[u]
    			RELAX(u,v,w)

举例：执行过程中，刚开始集合[![S][]][S 1]为空，则把集合[![V-S][]][V-S 1]中最短路径估计最小的节点[![u][]][u 1]加入到集合[![S][]][S 1]， 然后对从节点 [![u][]][u 1] 发出的边进行松弛。

第一步（图b）：将节点[![s][]][s 1]加入集合[![S][]][S 1]，并对节点[![s][]][s 1]所发出的边进行松弛操作；

第二步（图c）：在集合[![V-S][]][V-S 1]中最短路径估计最小的节点为[![y][]][y 1]，将节点[![y][]][y 1]加入到集合[![S][]][S 1]，并对节点[![y][]][y 1]所发出的边进行松弛操作；

第三步（图d）：在集合[![V-S][]][V-S 1]中最短路径估计最小的节点为[![z][]][z 1]，将节点[![z][]][z 1]加入到集合[![S][]][S 1]，并对节点[![z][]][z 1]所发出的边进行松弛操作；

第四步（图e）：在集合[![V-S][]][V-S 1]中最短路径估计最小的节点为[![t][]][t 1]，将节点[![t][]][t 1]加入到集合[![S][]][S 1]，并对节点[![t][]][t 1]所发出的边进行松弛操作；

第五步（图f）：在集合[![V-S][]][V-S 1]中最短路径估计最小的节点为[![x][]][x 1]，将节点[![x][]][x 1]加入到集合[![S][]][S 1]，并对节点[![x][]][x 1]所发出的边进行松弛操作；  
 ![SouthEast 2][]

[G_E_V]: http://latex.codecogs.com/gif.latex?G=%28E,V%29
[G_E_V_G_E_V]: /images/20220810/22dc667f6ee0435ca4ea2bd8f440a6a6.png
[s_epsilon V]: /images/20220810/99eb4429e37b4467ab0ea91b9edb84e7.png\epsilon&space;V
[s_epsilon V_s_epsilon V]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngs\epsilon&space;V
[v_epsilon V]: http://latex.codecogs.com/gif.latex?v\epsilon&space;V
[v_epsilon V_v_epsilon V]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngv\epsilon&space;V
[v.d]: http://latex.codecogs.com/gif.latex?v.d
[v.d 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngv.d
[s]: /images/20220810/99eb4429e37b4467ab0ea91b9edb84e7.png
[s 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngs
[u]: /images/20220810/10e7ec65c159486cb128e502cf4b3407.png
[u 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngu
[v]: http://latex.codecogs.com/gif.latex?v
[v 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngv
[v.front]: /images/20220810/42d39625bd0247a38dad7f060041ba87.png
[v.front 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngv.front
[SouthEast]: /images/20220810/da1528fe4cb64688bbdff62a3582ffbb.png
[V_-1]: http://latex.codecogs.com/gif.latex?|V|-1
[V_-1_V_-1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png|/images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png
[sigma _s_v]: http://latex.codecogs.com/gif.latex?\sigma&space;%28s,v%29
[sigma _s_v_sigma _s_v]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png\sigma&space;%28s,v%29
[t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y]: http://latex.codecogs.com/gif.latex?%28t,x%29,%28t,y%29,%28t,z%29,%28x,t%29,%28y,x%29,%28y,z%29,%28z,x%29,%28z,s%29,%28s,t%29,%28s,y%29
[t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y_t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_s_y]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png%28t,x%29,%28t,y%29,%28t,z%29,%28x,t%29,%28y,x%29,%28y,z%29,%28z,x%29,%28z,s%29,%28s,t%29,%28s,y%29
[t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t]: http://latex.codecogs.com/gif.latex?%28t,x%29,%28t,y%29,%28t,z%29,%28x,t%29,%28y,x%29,%28y,z%29,%28z,x%29,%28z,s%29,%28s,t%29
[t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t_t_x_t_y_t_z_x_t_y_x_y_z_z_x_z_s_s_t]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png%28t,x%29,%28t,y%29,%28t,z%29,%28x,t%29,%28y,x%29,%28y,z%29,%28z,x%29,%28z,s%29,%28s,t%29
[s_y]: http://latex.codecogs.com/gif.latex?%28s,y%29
[s_y_s_y]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.png%28s,y%29
[SouthEast 1]: /images/20220810/80f10693550e4938a0866992627ef358.png
[S]: http://latex.codecogs.com/gif.latex?S
[S 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngS
[V-S]: http://latex.codecogs.com/gif.latex?V-S
[V-S 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngV-S
[y]: /images/20220810/6ea6b56fb6334ecca2213c4c57c31306.png
[y 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngy
[z]: /images/20220810/86ab5db2979c43eab223cd2e1727f189.png
[z 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngz
[t]: /images/20220810/fc788ad7c2c9463789444e5aad4756eb.png
[t 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngt
[x]: /images/20220810/3b086838b9094bdfa19b009e532dd882.png
[x 1]: /images/20220810/9f5363afe19b4ca9aab3ddf7e4dc9344.pngx
[SouthEast 2]: /images/20220810/f1f0c9fae38945bd92c424de1f2512d7.png