首页 > 代码库 > 单源最短路径 Bellman_ford 和 dijkstra

单源最短路径 Bellman_ford 和 dijkstra

2024-09-04 09:22:45   222人阅读

首先两个算法都是常用于 求单源最短路径

关键部分就在于松弛操作 实际上就是dp的感觉

if (dist[e.to] > dist[v] + e.cost)

{

　　dist[e.to] = dist[v] + e.cost;　　

　　...

}

bellman_ford O(E*V) 但是配合队列可以 有spfa 可以达到O(kE) 

http://www.360doc.com/content/13/1208/22/14357424_335569176.shtml

并且bellman_ford还适用于负边 并且可以利用最多循环V-1次的性质 判断是否存在负圈(如果循环超过V-1次 说明有负圈 因为没重复走着负圈一次 都伴随着更新)

并且因为松弛操作是针对于每条边的遍历也可以用向前星存

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <fstream>
 4 #include <string.h>
 5 #define MAXV 10007
 6 #define MAXE 1007
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 
10 int V, E;
11 
12 struct Edge
13 {
14     int from, to, cost;
15 }edge[MAXE];
16 
17 
18 
19 
20 int bellman_ford(int s, int d)//求单源最短路径
21 {
22     int dist[MAXV];
23     fill (dist, dist+V+10, INF);
24     dist[s] = 0;
25     while (true)//直至update不在更新
26     {
27         bool update = false;
28         for (int i = 0; i < E; i++)
29         {
30             if (dist[edge[i].from] != INF && dist[edge[i].to] > dist[edge[i].from] + edge[i].cost)
31             {
32                 dist[edge[i].to] = dist[edge[i].from] + edge[i].cost;
33                 update = true;
34             }
35         }
36         if (!update) break;
37     }
38     return dist[d];
39 }
40 //while(true) 循环中最多循环V-1次 复杂度是O(V*E)
41 //如果存在 从s可达的负圈 那么在第V次循环时也会更新 可以用这个性质来检查负圈
42 //如果一开始把dist都初始化为0  那么可以检查出所有的负圈
43 //检查负边 是负边 返回true
44 //P.S 圈表示基本回路
45 bool isNegtive()
46 {
47     int dist[MAXV];
48     memset(dist, 0, sizeof(dist));//单纯查负圈
49     for (int i = 0; i < V; i++)
50     {
51         for (int i = 0; i < E; i++)
52         {
53             Edge e = edge[i];
54             if (dist[e.to] < dist[e.from] + e.cost )
55             {
56                 dist[e.to] = dist[e.from] + e.cost;
57                 if (i == V-1)//如果第V次还更新 那么就有负圈
58                     return true;
59             }
60         }
61     }
62     return false;
63 }
64 int main()
65 {
66     ifstream cin ("in.txt");
67     cin >> V >> E;
68     for (int i = 0; i < E; i++)
69     {
70         cin >> edge[i].from >> edge[i].to >> edge[i].cost;
71     }
72     cout << bellman_ford(1, 7) << endl;
73 }

dijkstra 普通写法O(V^2)

但是 dijkstra的特点 --->>是针对每一个点 通过它所对应的边更新 e.to的节点 

每次取出的是离原点sorce 最近的点 所以就可以使用优先队列 那么就变成O(V*logV)

并且因为“是针对每一个点 通过它所对应的边更新 e.to的节点 ” 那么也很好试用向前星

  1 #include <iostream>
  2 #include <string.h>
  3 #include <fstream>
  4 #include <stdio.h>
  5 #include <queue>
  6 #define MAXV 10007
  7 #define MAXE 1007
  8 #define INF 0x3f3f3f3f
  9 using namespace std;
 10 
 11 int V, E;
 12 //迪杰特斯拉好像不是很好用向前星
 13 //这个算法是针对每一个点更新 而向前星存储的是边的信息 要查找点就比较复杂
 14 
 15 //用邻接矩阵存储 O(V^2)的算法
 16 
 17 int cost[MAXV][MAXV];
 18 int dijkstra(int s, int d)
 19 {
 20     int dist[MAXV];
 21     bool use[MAXV];
 22     fill(dist, dist+MAXV, INF);
 23     memset(use, false, sizeof(use));
 24     dist[s] = 0;
 25     while (true)
 26     {
 27         int v = -1;
 28         for (int i = 1; i <= V; i++)//找一个最近的 未使用过的点
 29         {
 30             if (!use[i] && (v == -1 || dist[i] < dist[v])) v = i;
 31         }
 32         if (v == -1) break;
 33         use[v] = true;
 34         for (int i = 1; i <= V; i++)
 35         {
 36             dist[i] = min(dist[i], dist[v] + cost[v][i]);
 37         }
 38     }
 39     return dist[d];
 40 }
 41 
 42 //使用优先队列(也就是heap优化)O(E*logV)
 43 //针对边来dp 这里可以用向前星存储了
 44 struct Edge
 45 {
 46     int to, n, next;
 47 }edge[MAXE];
 48 int num = 0;
 49 int head[MAXV];
 50 void Add(int from, int to, int c)
 51 {
 52     edge[num].n = c;
 53     edge[num].to = to;
 54     edge[num].next = head[from];//从头插入
 55     head[from] = num++;
 56 }
 57 void init()//初始化
 58 {
 59     ifstream cin("in.txt");
 60     memset(edge, -1, sizeof(edge));
 61     memset(head, -1, sizeof(head));
 62     cin >> V >> E;
 63     for (int j = 0; j < E; j++)
 64     {
 65         int from , to , c;
 66         cin >> from >> to >> c;
 67         Add(from, to, c);
 68     }
 69 }
 70 
 71 typedef pair<int, int> P;//first 表示与s的距离, second表示点的编号
 72 int pre[MAXV];//记录前驱节点 在每次dist[j] = dist[k] + cost[k][j]更新时记录在到j的最短路径上的前驱节点就是k
 73 int fast_dijkstra(int s, int d)
 74 {
 75     int dist[MAXV];
 76     priority_queue<P, vector<P>, greater<P> > que;//用优先队列存储点的信息 每次弹出距离最短的点O(logV)
 77     fill(dist, dist+MAXV, INF);
 78     dist[s] = 0;
 79     que.push(P(0, s));
 80     while (!que.empty())
 81     {
 82         P p = que.top();
 83         que.pop();
 84         if (dist[p.second] < p.first) continue;
 85         int t = head[p.second];
 86         while (t != -1)
 87         {
 88             Edge e = edge[t];
 89             if (dist[e.to] > dist[p.second] + e.n)
 90             {
 91                 dist[e.to] = dist[p.second] + e.n;
 92                 pre[e.to] = p.second;
 93                 que.push( P(dist[e.to], e.to) );
 94             }
 95             t = e.next;
 96         }
 97     }
 98     return dist[d];
 99 }
100 
101 int main()
102 {
103     /*
104     ifstream cin("in.txt");
105     cin >> V >> E;
106     for (int i = 1; i <= V; i++)
107         for (int j = 1; j <= V; j++)
108             cost[i][j] = INF;//不存在时 cost为INF
109     for (int j = 0; j < E; j++)
110     {
111         int from , to , c;
112         cin >> from >> to >> c;
113         cost[from][to] = c;
114     }
115     int ans = dijkstra(1, 7);
116     */
117     init();
118     int ans = fast_dijkstra(1,7);
119     cout << ans << endl;
120     //这样路径即还原了
121     int t = pre[7];
122     cout << 7 << " ";
123     while(t != 1)
124     {
125         cout << t << " ";
126         t = pre[t];
127     }
128     cout << 1 <<endl;
129 }

 

单源最短路径 Bellman_ford 和 dijkstra


联系
我们