贝尔曼-福特算法(Bellman–Ford algorithm)
贝尔曼-福特算法是求解单源最短路径问题的一种算法,由 Richard Bellman \text{Richard Bellman} Richard Bellman 和 Lester Ford \text{Lester Ford} Lester Ford 创立的。有时候这种算法也被称为 Moore-Bellman-Ford \text{Moore-Bellman-Ford} Moore-Bellman-Ford 算法,因为 Edward F. Moore \text{Edward F. Moore} Edward F. Moore 也为这个算法的发展做出了贡献。它的原理是对图进行 ∣ V ∣ − 1 {\displaystyle |V|-1} ∣ V ∣ − 1 次松弛操作,得到所有可能的最短路径。其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单,缺点是时间复杂度过高,高达 O ( ∣ V ∣ ∣ E ∣ ) {\displaystyle O(|V||E|)} O ( ∣ V ∣∣ E ∣ ) 。但算法可以进行若干种优化,提高了效率。
迪杰斯特拉算法(Dijkstra’s algorithm)
算法思想
Dijkstra \text{Dijkstra} Dijkstra 算法是由荷兰计算机科学家 Dijkstra \text{Dijkstra} Dijkstra 在1956年发明的算法,并于3年后在期刊上发表。该算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。
该算法存在很多变体:原始版本仅适用于找到两个顶点之间的最短路径,后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径,产生一个最短路径树。
该算法解决了图 G = < V , E > {\displaystyle G=<V,E>} G =< V , E > 上带权的单源最短路径问题。具体来说,Dijkstra \text{Dijkstra} Dijkstra 算法设置了一顶点集合 S {\displaystyle S} S ,在集合 S {\displaystyle S} S 中所有的顶点与源点 s {\displaystyle s} s 之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点 u ∈ V − S {\displaystyle u\in {V-S}} u ∈ V − S 并将 u {\displaystyle u} u 加入 S {\displaystyle S} S 中。该算法常用于路由算法或者作为其他图算法的一个子模块。
应当注意,绝大多数的 Dijkstra \text{Dijkstra} Dijkstra 算法不能有效处理带有负权边的图。
(来源:WikiPedia )
过程模拟
设d i s [ i ] dis[i] d i s [ i ] 为点v 0 v_0 v 0 到v i v_i v i 的最短路径长度,我们要一次求出d i s [ 1 ] , d i s [ 2 ] , ⋯ , d i s [ 8 ] dis[1],dis[2] ,\cdots ,dis[8] d i s [ 1 ] , d i s [ 2 ] , ⋯ , d i s [ 8 ] 。
我们每次选择最小的d i s [ i ] dis[i] d i s [ i ] 并标记为访问,初始时d i s [ 0 ] = 0 , v i s [ 0 ] = 1 dis[0]=0,vis[0]=1 d i s [ 0 ] = 0 , v i s [ 0 ] = 1 。
显然d i s [ 1 ] = 1 dis[1]=1 d i s [ 1 ] = 1 ,我们标记v 1 v_1 v 1 已访问。由于v 1 v_1 v 1 还与v 2 , v 3 , v 4 v_2,v_3,v_4 v 2 , v 3 , v 4 相连,我们可以暂时设置d i s [ 2 ] = d i s [ 1 ] + w [ 1 ] [ 2 ] = 4 dis[2]=dis[1]+w[1][2]=4 d i s [ 2 ] = d i s [ 1 ] + w [ 1 ] [ 2 ] = 4 ,d i s [ 3 ] = d i s [ 1 ] + w [ 1 ] [ 3 ] = 8 dis[3]=dis[1]+w[1][3]=8 d i s [ 3 ] = d i s [ 1 ] + w [ 1 ] [ 3 ] = 8 ,d i s [ 4 ] = d i s [ 1 ] + w [ 1 ] [ 4 ] = 6 dis[4]=dis[1]+w[1][4]=6 d i s [ 4 ] = d i s [ 1 ] + w [ 1 ] [ 4 ] = 6 。
现在我们要求d i s [ 2 ] dis[2] d i s [ 2 ] ,如果说d i s [ 2 ] = 5 dis[2]=5 d i s [ 2 ] = 5 ,那么就错了,刚才的另一条路径已经得到d i s [ 2 ] = 4 < 5 dis[2]=4<5 d i s [ 2 ] = 4 < 5 ,我们标记v 2 v_2 v 2 已访问。由于v 2 v_2 v 2 还与v 4 , v 5 v_4,v_5 v 4 , v 5 连线,所以我们同时可以暂时设置d i s [ 4 ] = 5 , d i s [ 5 ] = 11 dis[4]=5,dis[5]=11 d i s [ 4 ] = 5 , d i s [ 5 ] = 11 。可以发现,这时d i s [ 4 ] dis[4] d i s [ 4 ] 已经被更新过了,得到了一个更小的值。
当我们要求d i s [ 3 ] dis[3] d i s [ 3 ] ,此时v 1 , v 2 v_1,v_2 v 1 , v 2 都已经被访问,我们从v 4 v_4 v 4 出发更新d i s [ 3 ] dis[3] d i s [ 3 ] ,得到d i s [ 3 ] = 7 dis[3]=7 d i s [ 3 ] = 7 ,v i s [ 4 ] = 1 vis[4]=1 v i s [ 4 ] = 1 。
⋯ ⋯ \cdots\cdots ⋯⋯ 可以按照上述过程一直推到d i s [ 8 ] dis[8] d i s [ 8 ] 。
可以看到,我们每次选择距离v 0 v_0 v 0 最近(d i s [ i ] dis[i] d i s [ i ] 最小)且还未被标记访问的点,从该点出发更新所有的d i s [ i ] dis[i] d i s [ i ] ,称之为松弛操作。
例题
Description
Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.
Farmer John’s field has N N N ( 2 ⩽ N ⩽ 1000 ) (2\leqslant N\leqslant 1000) ( 2 ⩽ N ⩽ 1000 ) landmarks in it, uniquely numbered 1.. N 1..N 1.. N . Landmark 1 1 1 is the barn; the apple tree grove in which Bessie stands all day is landmark N N N . Cows travel in the field using T T T ( 1 ⩽ T ⩽ 2000 ) (1\leqslant T\leqslant 2000) ( 1 ⩽ T ⩽ 2000 ) bidirectional cow-trails of various lengths between the landmarks. Bessie is not confident of her navigation ability, so she always stays on a trail from its start to its end once she starts it.
Given the trails between the landmarks, determine the minimum distance Bessie must walk to get back to the barn. It is guaranteed that some such route exists.
Line 1: Two integers: T T T and N N N
Lines 2…T+1: Each line describes a trail as three space-separated integers. The first two integers are the landmarks between which the trail travels. The third integer is the length of the trail, range 1…100.
Output
Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N N N to landmark 1 1 1 .
5 5
1 2 20
2 3 30
3 4 20
4 5 20
1 5 100
Sample Output
90
Hint
There are five landmarks.
OUTPUT DETAILS
Bessie can get home by following trails 4, 3, 2, and 1.
Translation
一张图有t t t 条边,n n n 个点,求从节点1 1 1 至节点n n n 的最短路径长度。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 #include <iostream> #include <cstring> #include <algorithm> #define N 1002 #define inf 0x3f3f3f3f using namespace std;int G[N][N];int t,n;bool vis[N];int dis[N];void dijkstra () { int i,j; for (i=1 ;i<=n;i++) dis[i]=G[1 ][i]; int res,pos; vis[1 ]=1 ; for (i=1 ;i<=n;i++) { res=inf; for (j=1 ;j<=n;j++) { if (res>dis[j]&&!vis[j]) { pos=j; res=dis[j]; } } vis[pos]=1 ; for (j=1 ;j<=n;j++) { if (!vis[j]&&dis[j]>dis[pos]+G[pos][j]) { dis[j]=dis[pos]+G[pos][j]; } } } cout<<dis[n]<<endl; } void solve () { memset (G,inf,sizeof (G)); cin>>t>>n; int i; for (i=1 ;i<=n;i++) G[i][i]=0 ; while (t--) { int u,v,w; cin>>u>>v>>w; G[u][v]=min (G[u][v],w); G[v][u]=min (G[v][u],w); } dijkstra (); } int main () { solve (); return 0 ; }
优化
链式前向星优化
能极大降低空间复杂度,由于链式前向星可以存两点之间的很多边,所以不需要考虑去重边。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 #include <iostream> #include <cstring> #include <algorithm> #define N 5300 using namespace std;int head[N];int tot;struct E { int to; int Next; int w; }edge[N]; void add_edge (int from,int to,int w) { tot++; edge[tot].to=to; edge[tot].w=w; edge[tot].Next=head[from]; head[from]=tot; } int t,n;bool vis[N];int dis[N];void dijkstra () { int i,j; memset (dis,0x3f ,sizeof (dis)); memset (vis,0 ,sizeof (vis)); int res,pos; dis[1 ]=0 ; for (i=1 ;i<=n;i++) { res=0x3f3f3f3f ; for (j=1 ;j<=n;j++) { if (res>dis[j]&&!vis[j]) { pos=j; res=dis[j]; } } vis[pos]=1 ; for (j=head[pos];j!=-1 ;j=edge[j].Next) { int y=edge[j].to; if (!vis[y]&&dis[y]>dis[pos]+edge[j].w) { dis[y]=dis[pos]+edge[j].w; } } } cout<<dis[n]<<endl; } void solve () { memset (head,-1 ,sizeof (head)); cin>>t>>n; while (t--) { int u,v,w; cin>>u>>v>>w; add_edge (u,v,w); add_edge (v,u,w); } dijkstra (); } int main () { solve (); return 0 ; }
堆优化
堆优化可将时间复杂度降至O ( ( m + n ) log n ) O((m+n)\log n) O (( m + n ) log n ) 。使用一个优先队列来代替最短距离的查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 #include <iostream> #include <cstring> #include <vector> #include <queue> #define N 5044 using namespace std;int head[N];int tot;struct cmp { template <typename T> bool operator () (T const & left,T const & right) { if (left.second>right.second) return true ; else return false ; } }; struct E { int to; int Next; int w; }edge[N]; void add_edge (int from,int to,int w) { tot++; edge[tot].to=to; edge[tot].w=w; edge[tot].Next=head[from]; head[from]=tot; } int t,n;bool vis[N];int dis[N];void dijkstra () { int i,j; memset (dis,0x3f ,sizeof (dis)); memset (vis,0 ,sizeof (vis)); int res,pos; dis[1 ]=0 ; priority_queue<pair<int ,int >,vector<pair<int ,int > >,cmp>q; q.push (make_pair (1 ,0 )); while (!q.empty ()) { pair<int ,int >res; res=q.top (); q.pop (); int from=res.first; vis[from]=1 ; for (j=head[from];j!=-1 ;j=edge[j].Next) { int to=edge[j].to; if (!vis[to]&&dis[to]>dis[from]+edge[j].w) { dis[to]=dis[from]+edge[j].w; q.push (make_pair (to,dis[to])); } } } cout<<dis[n]; } void solve () { memset (head,-1 ,sizeof (head)); cin>>t>>n; while (t--) { int u,v,w; cin>>u>>v>>w; add_edge (u,v,w); add_edge (v,u,w); } dijkstra (); } int main () { solve (); return 0 ; }
模板
题目描述
给定一个 n n n 个点,m m m 条有向边的带非负权图,请你计算从 s s s 出发,到每个点的距离。
数据保证你能从 s s s 出发到任意点。
输入格式
第一行为三个正整数 n , m , s n, m, s n , m , s 。 第二行起 m m m 行,每行三个非负整数 u i , v i , w i u_i, v_i, w_i u i , v i , w i ,表示从 u i u_i u i 到 v i v_i v i 有一条权值为 w i w_i w i 的有向边。
输出格式
输出一行 n n n 个空格分隔的非负整数,表示 s s s 到每个点的最短距离。
输入输出样例
输入 #1
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4
输出 #1
0 2 4 3
说明/提示
1 ≤ n ≤ 1 0 5 1 \leq n \leq 10^5 1 ≤ n ≤ 1 0 5 ;
1 ≤ m ≤ 2 × 1 0 5 1 \leq m \leq 2\times 10^5 1 ≤ m ≤ 2 × 1 0 5 ;
1 ≤ u i , v i ≤ n 1 \leq u_i, v_i\leq n 1 ≤ u i , v i ≤ n ;
0 ≤ ∑ w i ≤ 1 0 9 0 \leq \sum w_i \leq 10 ^ 9 0 ≤ ∑ w i ≤ 1 0 9 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 #include <cstdio> #include <algorithm> #include <queue> #define N 100002 using namespace std;struct E { int to; int w; int Next; }edge[N<<1 ]; int head[N],tot;int dis[N];bool vis[N];int n,m,s;inline void add (int u,int v,int w) { tot++; edge[tot].to=v; edge[tot].w=w; edge[tot].Next=head[u]; head[u]=tot; } struct node { int id; int dis; bool operator <(const node &x)const { return x.dis<dis; } }; void dijkstra () { fill (dis,dis+1 +n,0x7fffffff ); dis[s]=0 ; int i; priority_queue<node>q; q.push ((node){s,0 }); while (!q.empty ()) { node now=q.top (); q.pop (); int x=now.id; if (vis[x]) continue ; vis[x]=1 ; for (i=head[x];~i;i=edge[i].Next) { int y=edge[i].to; if (!vis[y]&&dis[y]>dis[x]+edge[i].w) { dis[y]=dis[x]+edge[i].w; q.push ((node){y,dis[y]}); } } } for (i=1 ;i<=n;i++) printf ("%d " ,dis[i]); } int main () { scanf ("%d%d%d" ,&n,&m,&s); fill (head,head+n+1 ,-1 ); while (m--) { int u,v,w; scanf ("%d%d%d" ,&u,&v,&w); add (u,v,w); } dijkstra (); return 0 ; }