简介
Dijkstra算法是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
无优化复杂度：O(n ^ 2)
那么有O（km）的Spfa算法我们为什么需要Dijkstra算法呢？
因为某些毒瘤出题人会专门设计网格图来卡Spfa算法，使其变为O（m ^ 2）如下方提到的落谷题目。
洛谷：P3371（弱化版） Spfa能过 P4779（标准版）卡Spfa
普通算法
这是Dijkstra的普通算法（无优化）复杂度O（n ^ 2）
|
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 <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; static const int MAXN = 100005; static const int MAXM = 200005; static const int INF = 2147483647; struct node { int dis; int next; int to; } e[MAXM]; int head[MAXN],cnt,n,m,s; int dis[MAXN]; bool vis[MAXN]; void add(int ,int ,int ); void Init(); void Dijkstra(); int main() { scanf("%d%d%d",&n,&m,&s); for(int i = 1;i <= m;++i) { int from,to,dis; scanf("%d%d%d",&from,&to,&dis); add(from,to,dis); } Dijkstra(); for(int i = 1;i <= n;++i) printf("%d ",dis[i]); return 0; } void add(int from,int to,int dis) { e[++cnt].next = head[from]; e[cnt].to = to; e[cnt].dis = dis; head[from] = cnt; } void Init() { for(int i = 1;i <= n;++i) dis[i] = (i == s ? 0 : INF); } void Dijkstra() { Init(); for(int i = 1;i <= n;++i) { int flag = 214748364,t = -1; for(int j = 1;j <= n;++j) if(!vis[j] && dis[j] < flag) { flag = dis[j]; t = j; } if(t == -1) break; vis[t] = true; for(int j = head[t];j;j = e[j].next) if(!vis[e[j].to]) dis[e[j].to] = min(dis[e[j].to],dis[t] + e[j].dis); } } |
堆优化
这是Dijkstra算法的堆优化。复杂度为O（nlogn）
|
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 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; static const int MAXN = 100005; static const int MAXM = 200005; static const int INF = 2147483647; struct node { int dis; int next; int to; } e[MAXM]; int head[MAXN],cnt,n,m,s; int dis[MAXN]; bool vis[MAXN]; void add(int ,int ,int ); void Init(); void Dijkstra_Heap(); int main() { scanf("%d%d%d",&n,&m,&s); for(int i = 1;i <= m;++i) { int from,to,dis; scanf("%d%d%d",&from,&to,&dis); add(from,to,dis); } Dijkstra_Heap(); for(int i = 1;i <= n;++i) printf("%d ",dis[i]); return 0; } void add(int from,int to,int dis) { e[++cnt].next = head[from]; e[cnt].to = to; e[cnt].dis = dis; head[from] = cnt; } void Init() { for(int i = 1;i <= n;++i) dis[i] = (i == s ? 0 : INF); } void Dijkstra_Heap() { priority_queue <pair <int ,int > ,vector <pair <int ,int > >,greater <pair <int ,int > > > Q; Init(); Q.push(make_pair(0,s)); while(!Q.empty()) { int u = Q.top().second; Q.pop(); if(vis[u]) continue; vis[u] = true; for(int i = head[u];i;i = e[i].next) { int v = e[i].to; if(dis[v] > dis[u] + e[i].dis) { dis[v] = dis[u] + e[i].dis; if(!vis[v]) Q.push(make_pair(dis[v],v)); } } } } |
