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

发布时间:2024年01月07日

先看一眼原始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";
}

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135443760
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。