[算法应用]dijkstra算法的应用

本文主要是介绍[算法应用]dijkstra算法的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

先看一眼原始dijkstra算法，参考自dijkstra算法C++实现_c++实现djikstra-CSDN博客

分为三步

1. 找到当前最优的
2. 把当前最优的，不参与后面的更新
3. 逐个比较是否更新

dijkstra算法的应用

题目大概是要从图上找一条权值不减的路径，且要经过最多的点。

所以用 Dijsktra 更新的原则是，1到该点的经过的点更多，则更新。

使用优先队列自动排序，排序的原则是：

1. 首先，如果这两个点的权值，a>b，那么在优先级里，a<b（解释：要选权值更小的点，因为权值更大的话，就不是不减了）
2. 接着，如果两点权值相等，就让1到该点经过的点更多的那个点优先（解释：我们的目的就是找点最多的那条路）

附上大佬的代码

struct T {int fi, se;friend bool operator < (T x, T y) {if (a[x.se] == a[y.se]) {if (x.fi == y.fi) return x.se > y.se;else return x.fi < y.fi;}else return a[x.se] > a[y.se];}
};
void dijkstra() {priority_queue<T> que;que.push({1, 1}); d[1] = 1;while (que.size()) {T p = que.top(); que.pop();int u = p.se, w = p.fi;if (st[u]) continue;st[u] = true;for (auto v : e[u]) {if (a[v] < a[u]) continue;int nw = d[u] + (a[v] != a[u]);if (nw > d[v]) {d[v] = nw;que.push({d[v], v});}}}cout << d[n] << "\n";
}

这篇关于[算法应用]dijkstra算法的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---