Loading... 最短路问题是图和树问题中常见的问题，Dijkstra算法又是一种较为常见的最短路算法，所以...好用，嗯嗯，好用 ## 单源最短路径问题 ...在一张有向图上，节点以[1,n]之间连续整数编号，(x,y,z)描述一条从x到y长度为z的有向边。dist[i]表示从起点1到节点i的最短路径长度。 ## Dijkstra **算法流程**： 1. 初始化dist[1]=0，其余节点为正无穷大 2. 找出一个未被标记的、dist[x]最小的节点x，然后标记它 3. 扫描节点x的所有出边(x,y,z)，若dist[y]>dist[x]+z则用dist[x]+z更新dist[y] 4. 重复步骤2、3，直到所有节点都被标记 这明摆着是一个贪心算法。以起点出发，不断选择全局未标记的、离起点最近的节点标记和扩展，最终可以得到所有节点到起点的最短路径长度。 因为第一步选出的节点1必须满足dist[1]=0不能被其他节点更新，所以所有边的长度都应大于等于dist[1]，即Dijkstra算法只适用于所有边的长度都是非负数的图 下面的代码演示了Dijkstra算法的一般实现方式。 ```cpp #include <iostream> #include <algorithm> using namespace std; int n, m, a[3010][3010]/*邻接矩阵*/, dist[3010]; bool v[3010]; void dijkstra(){ fill(dist, dist+n+1, 1e9); dist[1] = 0; for(int i = 1; i < n; ++i){ int x = 0; //找到未被标记的、dist[x]最小的节点x for(int j = 1; j <= n; ++j){ if(!v[j] && dist[j] < dist[x]) x = j; } //标记x v[x] = 1; //扫描节点x的所有出边(x,y,z) for(int y = 1; y <= n; ++y){ if(a[x][y]) dist[y] = min(dist[y], dist[x]+a[x][y]); } } } int main(){ cin >> n >> m; for(int i = 0; i < m; ++i){ int x, y, z; cin >> x >> y >> z; a[x][y] = z; } dijkstra(); for(int i = 1; i <= n; ++i){ cout << dist[i] << endl; } return 0; } ``` 要注意的是，上面代码在第3步扫描节点x出边时，为了简便，当a[x]\[y]=0时视作无边，即所有边为正数。如果考虑长度为0的边，可以先将所有边赋正无穷大，特殊地，a[i]\[i]=0，再覆盖输入。这样第3步时就不需判断，因为当有向边(x,y)不存在，dist[x]+a[x]\[y]必定大于dist[y]，dist[y]也不会被更新。 上面程序的时间复杂度为$O(n^2) ## Heap-Dijkstra 朴素Dijkstra算法时间复杂度的主要瓶颈是第一步寻找全局最小值的过程。用小根二叉堆对dist数组进行维护，最终可将时间复杂度降至$O((m+n) \log n)$ C++STD**priority_queue**类可理解为大根二叉堆，其中储存的元素必须定义“小于号”。**pair**类定义了“小于号”，默认以first元素比较。所以储存first元素的相反数，取出时取反。这样就可以实现小根堆。 ```cpp #include <iostream> #include <queue> #include <algorithm> using namespace std; int n, m, a[3010][3010], dist[3010]; bool v[3010]; priority_queue<pair<int/*-dist[i]*/, int/*i*/> > heap; //小根堆 void heap_dijkstra(){ fill(dist, dist+n+1, 1e9); dist[1] = 0; heap.push((pair<int, int>){0, 1}); while(!heap.empty()){ int x = heap.top().second; heap.pop(); if(v[x]) continue; v[x] = 1; for(int y = 1; y <= n; ++y){ if(a[x][y]){ dist[y] = min(dist[y], dist[x]+a[x][y]); heap.push((pair<int, int>){-dist[y], y}); } } } } int main(){ cin >> n >> m; for(int i = 0; i < m; ++i){ int x, y, z; cin >> x >> y >> z; a[x][y] = z; } heap_dijkstra(); for(int i = 1; i <= n; ++i){ cout << dist[i] << endl; } return 0; } ``` © 允许规范转载 赞赏 如果我的文章对你有用，请随意赞赏 ×Close 赞赏作者 扫一扫支付 微信支付
