算法简介
Dijkstra算法是一种求最短路的算法,在使用优先队列进行优化后时间复杂度比较优秀。
算法原理
如果图是不带负权的有向图或者无向图,我们可以从s
点开始寻找它的所有出边,与数组dis
(每个点离原点s
点的最短距离)进行比较,如果有小于dis[v]
的路径,则松弛该点,最后可以得到一个所有最短路径的表。
算法步骤
- 初始化
dis
数组,原点赋值为0
,其它点全部赋值为INF
(为原点到该点的距离)。
- 重复
n
次操作,找到x
的所有出边,对需要进行松弛的边进行松弛。
该算法的时间复杂度为$O(n^2)$,使用优先队列优化后的算法时间复杂度为$O((n+m)\log m)$。
文中代码边的存储使用链式前向星实现。
算法模板
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
| #include <iostream> #include <cstring> #include <queue> #include <algorithm> using namespace std;
const int INF = 0x7fffffff; const int MAXN = 5 * 10e5 + 5; int n, m, s; int dis[MAXN], book[MAXN], head[MAXN], cnt = 1; priority_queue<pair<int, int> > que;
struct Edge { int next, to, w; } e[MAXN];
void add(int u, int v, int w) { e[cnt].w = w; e[cnt].to = v; e[cnt].next = head[u]; head[u] = cnt++; }
int main() { cin >> n >> m >> s; memset(head, -1, sizeof(head)); memset(book, 0, sizeof(book)); fill(dis, dis + MAXN, INF);
for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; add(u, v, w); }
dis[s] = 0; que.push({0, s}); while (!que.empty()) { int x = que.top().second; que.pop();
if (book[x]) continue; book[x] = 1;
for (int i = head[x]; i != -1; i = e[i].next) { int v = e[i].to; if (dis[v] > dis[x] + e[i].w) { dis[v] = dis[x] + e[i].w; que.push({-dis[v], v}); } } }
for (int i = 1; i <= n; i++) cout << dis[i] << " "; cout << endl; return 0; }
|