首页 > 代码库 > [Algotithm] 最短路之旅
[Algotithm] 最短路之旅
这可能是非常久以前的东西。
不过想想复习一下也是好的（其实是发现居然不会dijkstra了）。
一、通用原理
维护一个数组记录所有点的最短路。
枚举边确认是否可以通过这条边减小其它点的最短距离。
得出答案。
二、主流算法
A. Dijkstra
Dijkstra，荷兰人。
Dijkstra要求提供两个点集，分别用于存放不再修改的点与待修改的点（也就是是否找到最短路）
显然第一个不再修改的点是起点，且其最短路为0。
那么，首先找到已知的最短路径最短的点（想象一个凸多边形，哪里离中心最近就哪里进行扩张）。
然后这个点扔进不再修改的点集（记为A）。
然后枚举其边以更新其它点的最短路。
显然，这种方式将持续n次，因为每次都必然扔且只扔一个点进去点集A。
然后查找的过程又是n次。
最后枚举边如果用邻接矩阵的话也是n次，如果用邻接表的话可以E（E是边数）。
PS：我并不是说准确次数啊，n-1 接近 n 所以我直接说 n QwQ
那么朴素dijkstra的复杂度就是O(n^2+nE)，近似看作O(n^2)。
堆优化：
想要减小时间复杂度，第一个要优化的就是查找枚举基点的过程，毕竟每次都O(n)。
这段部分就其根本是要找到可修改的最短距离。
那么我们可以用一个堆（或优先队列）代替原来的朴素队列使得我们要找的最小dis每次就在堆顶。
题目：
单源最短路：https://www.luogu.org/problem/show?pid=3371
这道题数据还算不错。
注意：数据大小需要注意。
1 #include<cstdio> 2 #include<iostream> 3 #include<queue> 4 #define maxn_P 10101 5 #define maxn_E 505050 6 #define INF 2147483647 7 using namespace std; 8 typedef pair<int,int> node; 9 10 struct edge{11 int from,v,len;12 }e[maxn_E];13 14 int first[maxn_P],tot,dis[maxn_P],n,m,s,a,b,c;15 bool book[maxn_P];16 17 void insert(int u,int v,int len){18 tot++;19 e[tot].from = first[u];20 e[tot].v = v;21 e[tot].len = len;22 first[u] = tot;23 }24 25 void dijkstra(){26 for(int i = 1;i <= n;i++) dis[i] = INF;27 28 priority_queue<node,vector<node>,greater<node> > q;29 30 dis[s] = 0;31 32 q.push(make_pair(dis[s],s));33 34 while(!q.empty()){35 node tmp = q.top();36 q.pop();37 int p = tmp.second;38 39 if(!book[p]){40 book[p] = true;41 for(int i = first[p];i;i = e[i].from){42 if(dis[e[i].v] > dis[p]+e[i].len){43 dis[e[i].v] = dis[p]+e[i].len;44 q.push(make_pair(dis[e[i].v],e[i].v));45 }46 }47 }48 } 49 }50 51 int main(){52 scanf("%d%d%d",&n,&m,&s);53 54 for(int i = 0;i < m;i++){55 scanf("%d%d%d",&a,&b,&c);56 insert(a,b,c);57 }58 59 dijkstra();60 61 for(int i = 1;i <= n;i++){62 printf("%d ",dis[i]);63 }64 65 return 0;66 }
To be filled
[Algotithm] 最短路之旅