最短路之dijkstra及其堆优化

解决问题

dijkstra算法用来解决单源最短路径问题 通常来说就是求解一个图中两节点的最短路径（只适用于正权边）

算法思想

该算法的朴素想法是松弛的思想 即若 dis ( 1->3 ) = 7 dis ( 1->2 ) = 1 dis ( 2->3 ) = 1 则节点2的存在就可以对1，3松弛 在松弛完一个节点之后要选择尚未进行松弛的节点松弛，且要选择距起点距离最近的点【1】

代码实现

///朴素dijkstra O(n^2+m) int g[N][N]; // 存储每条边 int dist[N]; // 存储1号点到每个点的最短距离 bool st[N]; // 存储每个点的最短路是否已经确定 // 求1号点到n号点的最短路，如果不存在则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == -1 || dist[t] > dist[j])) t = j; // 用t更新其他点的距离 for (int j = 1; j <= n; j ++ ) dist[j] = min(dist[j], dist[t] + g[t][j]); st[t] = true; } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } ///代码是从y总那偷的QAQ ///堆优化的dijkstra O(mlogn) typedef pair<int, int> PII;///改用结构体也可 int n; // 点的数量 int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边 int dist[N]; // 存储所有点到1号点的距离 bool st[N]; // 存储每个点的最短距离是否已确定 // 求1号点到n号点的最短距离，如果不存在，则返回-1 int dijkstra() { memset(dist, 0x3f, sizeof dist); dist[1] = 0; priority_queue<PII, vector<PII>, greater<PII>> heap; heap.push({0, 1}); // first存储距离，second存储节点编号 while (heap.size()) { auto t = heap.top(); heap.pop(); int ver = t.second, distance = t.first; if (st[ver]) continue; st[ver] = true; for (int i = h[ver]; i != -1; i = ne[i]) { int j = e[i]; if (dist[j] > distance + w[i]) { dist[j] = distance + w[i]; heap.push({dist[j], j}); } } } if (dist[n] == 0x3f3f3f3f) return -1; return dist[n]; } ///代码是从y总那偷的QAQ ///自己写的比较顺手的dij #include<bits/stdc++.h> using namespace std; struct edge { int to; int l; }; struct node { int idx; int l; bool friend operator < (const node a, const node b) { return a.l>b.l; } } d[100005]; const int inf=0x3f3f3f3f; vector<edge> ve[100005]; priority_queue<node> qu; bool vis[100005]; void build(int u,int v,int l) { edge t; t.to=v,t.l=l; ve[u].push_back(t); } int main() { int n,m,s; scanf("%d%d%d",&n,&m,&s); for(int i=1; i<=m; i++) { int u,v,l; scanf("%d%d%d",&u,&v,&l); build(u,v,l); } for(int i=1; i<=n; i++) d[i].l=inf,d[i].idx=i; d[s].l=0; qu.push(d[s]); while(!qu.empty()) { node temp=qu.top(); qu.pop(); if(vis[temp.idx]) continue; vis[temp.idx]=1; int big=ve[temp.idx].size(); for(int i=0; i<big; i++) { if(d[temp.idx].l+ve[temp.idx][i].l<d[ve[temp.idx][i].to].l) { d[ve[temp.idx][i].to].l =d[temp.idx].l+ve[temp.idx][i].l; qu.push(d[ve[temp.idx][i].to]); } } } for(int i=1; i<=n; i++) printf("%d ",d[i].l); return 0; }

【1】 因为该节点一定无法距起点更近