首页 > Web开发 > 详细

学习记录:Dijstra最短路

时间:2020-08-05 13:02:30      阅读:78      评论:0      收藏:0      [点我收藏+]

学习记录:Dijstra最短路

其实Dijstra早学过,这次主要写点用邻接表和堆优化的东西

想法

Dijstra的想法其实很简单,维护一个已经达到最短路线的点的集合即可。

从出发点开始,找到距离出发点最近的那个点加入集合,重复此步骤直至所有点都加入集合即可。

原因很简单,设出发点为\(s\),距离\(s\)最近的点是\(i\)\(Dis[i]<Dis[其他点]+其他点到点i的距离\),因此最近的点就加入集合了。

邻接矩阵实现的Dijstra

最简单的Dij,但是过不了[洛谷弱化版的模板题][https://www.luogu.com.cn/problem/P3371],空间占用大,但是方便理解Dij的思路

int Map[maxn][maxn];
int vis[maxn];
ll dis[maxn];
int n, m, s;
void Dij()
{
	for (int i = 1; i <= n; i++)
		dis[i] = Map[s][i];
	dis[s] = 0;
	vis[s] = 1;
	for (int j = 1; j <= n; j++)
	{
		int flag = 0;
		for (int i = 1; i <= n; i++)
			if (!vis[i] && (dis[i] < dis[flag] || flag == 0))
				flag = i;
		vis[flag] = 1;
		for (int i = 1; i <= n; i++)
			if (!vis[i])
				dis[i] = min(dis[i], dis[flag] + Map[flag][i]);
	}
}
int main()
{
	cin >> n >> m >> s;
	while (m--)
	{
		int u, v, w;
		cin >> u >> v >> w;
		Map[u][v] = min(w, Map[u][v]);//洛谷的数据最坑的就是有重边...
	}
	Dij();
	for (int i = 1; i <= n; i++)
		cout << dis[i] << ‘ ‘;
	return 0;
}

邻接表实现的Dijstra

这样就可以过模板题了。用的vector实现。

struct node
{
	int to, val;
	node(int to, int val) : to(to), val(val) {}
};
ll n, m, s;
ll dis[maxn];
int vis[maxn];
vector<node> Map[maxn];
void Dij()
{
	for (int i = 0; i <= n; i++)
		dis[i] = INF;
	dis[s] = 0;//这里没有初始化dis数组,是因为接下来的循环可以直接初始化
	for (int k = 0; k < n; k++)
	{
		int kk = 0;
		for (int i = 1; i <= n; i++)
			if (!vis[i] && dis[i] < dis[kk])
				kk = i;
		vis[kk] = 1;
		for (int i = 0; i < Map[kk].size(); i++)
			if (dis[Map[kk][i].to] > dis[kk] + Map[kk][i].val)
				dis[Map[kk][i].to] = dis[kk] + Map[kk][i].val;
	}
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 0, a, b, c; i < m; i++)
	{
		cin >> a >> b >> c;
		Map[a].push_back(node(b, c));
	}
	Dij();
	for (int i = 1; i <= n; i++)
		cout << dis[i] << ‘ ‘;
	return 0;
}

堆优化的Dijstra

struct node
{
	int to, val;
	node(int to, int val) : to(to), val(val) {}
};
int n, m, s;
vector<node> Map[maxn];
int vis[maxn], dis[maxn];

typedef pair<int, int> P;
void Dij()
{
	priority_queue<P, vector<P>, greater<P>> q;
	MS(dis, INF);
	dis[s] = 0;
	q.push(P(0, s));
	while (!q.empty())
	{
		P p = q.top();
		q.pop();
		int index = p.second;
		if (dis[index] < p.first)
			continue;
		for (int i = 0; i < Map[index].size(); i++)
		{
			node e = Map[index][i];
			if (dis[e.to] > dis[index] + e.val)
			{
				dis[e.to] = dis[index] + e.val;
				q.push(P(dis[e.to], e.to));
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s;
	for (int i = 1, x, y, z; i <= m; i++)
	{
		cin >> x >> y >> z;
		Map[x].push_back(node(y, z));
	}
	Dij();
	for (int i = 1; i <= n; i++)
		cout << dis[i] << ‘ ‘;
	return 0;
}

学习记录:Dijstra最短路

原文:https://www.cnblogs.com/Salty-Fish/p/13439063.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!