[数据结构与算法]朴素版Dijkstra算法+堆排序优化版

朴素版Dijkstra算法

题目链接–Dijkstra求最短路径

关键代码

int Dijkstra()
{
	dist[1] = 0;

	for (int i = 1; i <= n; i++){
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!vis[j] && (t == -1 || dist[j] < dist[t]))
				t = j;
		vis[t] = true;
		for (int j = 1; j <= n; j++)
				dist[j] = min(dist[j],dist[t] + path[t][j]);
	}
	return dist[n];
}

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 510;
int n, m, path[N][N], dist[N];
//path存两点的距离，dist存第i节点到1节点的最短距离
bool vis[N];
int Dijkstra()
{
	dist[1] = 0;

	for (int i = 1; i <= n; i++)//对剩余n-1个节点更新最短距离
	{
		int t = -1;
		for (int j = 1; j <= n; j++)
			if (!vis[j] && (t == -1 || dist[j] < dist[t]))
				t = j;//找到未访问过的节点中距离节点1最小的节点
		vis[t] = true;
		for (int j = 1; j <= n; j++)
				dist[j] = min(dist[j],dist[t] + path[t][j]);
				//min是选择重边里的距离最小的边
		//更新节点t相邻未访问过的边的最小值
		//一开始我先判断了j是否被访问过，但发现一点不影响，如果j被访问过，j一定在t之前或者就是t，所以dist[j]<=dist[t]
	}
	return dist[n];
}
int main()
{
	cin >> n >> m;
	//Inti
	memset(path, 0x3f, sizeof path);//为什么这里是0x3f,后面有解释
	memset(dist, 0x3f, sizeof dist);
	int x, y, v;
	while (m--)
	{
		cin >> x >> y >> v;
		path[x][y]=min(v,path[x][y]);
	}
	int ret = Dijkstra();

	if (ret != 0x3f3f3f3f) cout << ret;
	else cout << -1;
	return 0;
}

• 关于定义无穷为0x3f3f3f3f而不取0x7fffffff详细见这篇博客
  简单说就是用0x7fffffff可能会使无穷+无穷数据溢出，变成负数，而0x3f3f3f3f不会
• 关于memset( ,0x3f,sizeof ):
  如果我们想要将某个数组清零，我们通常会使用memset(a,0,sizeof(a))这样的代码来实现（方便而高效），但是当我们想将某个数组全部赋值为无穷大时（例如解决图论问题时邻接矩阵的初始化），就不能使用memset函数而得自己写循环了（写这些不重要的代码真的很痛苦），我们知道这是因为memset是按字节操作的，它能够对数组清零是因为0的每个字节都是0，现在好了，如果我们将无穷大设为0x3f3f3f3f，那么奇迹就发生了，0x3f3f3f3f的每个字节都是0x3f！所以要把一段内存全部置为无穷大，我们只需要memset(a,0x3f,sizeof(a))。

堆排序优化版Dijkstra

题目链接–Dijkstra求最短路径Ⅱ

关于优先队列priority_queue函数的使用:

头文件#include<queue>
定义：priority_queue<Type, Container, Functional>
Type 就是数据类型，Container 就是容器类型（Container必须是用数组实现的容器，比如vector,deque等等，但不能用 list。STL里面默认用的是vector），Functional 就是比较的方式。
greater<Type>是小根堆，less<Type>是大根堆

 //升序队列，小顶堆
2 priority_queue <int,vector<int>,greater<int> > q;
3 //降序队列，大顶堆
4 priority_queue <int,vector<int>,less<int> >q;

完整代码

思路和朴素版的其实一样
关键代码

int Dijkstra()
{
	heap.push({ 0,1 });
	while (!heap.empty()) {
		PII temp = heap.top();
		heap.pop();
		int node = temp.second, distance = temp.first;
		if (vis[node]) continue;
		vis[node] = true;
		for (int i = h[node]; i != -1; i = ne[i])
			if (distance + W[i] < dist[e[i]]) {
				dist[e[i]] = W[i] + distance;
				heap.push({ dist[e[i]],e[i] });
			}

	}
	return dist[n];
}

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>//通过优先队列实现堆排序减小时间复杂度
#include<cstring>
using namespace std;
typedef pair<int, int>PII;
const int N = 1.5 * 1e5 + 5;
int h[N], e[N], ne[N], W[N], idx, n, dist[N];
bool vis[N];
priority_queue<PII, vector<PII>, greater<PII>>heap;
//第一个元素存的是dist，第二个存的是节点,先比较第一个元素再比较第二个元素
//e寸的仍然是节点，W存的是节点到该条链头结点的距离（两节点之间的距离)
void add(int x, int y, int w)//x->y
{
	e[idx] = y; ne[idx] = h[x]; W[idx] = w; h[x] = idx++;
}
int Dijkstra()
{
	heap.push({ 0,1 });
	dist[1] = 0;
	while (!heap.empty())
	{
		PII temp = heap.top();//最小堆直接得到dist最小的节点
		heap.pop();
		int node = temp.second, distance = temp.first;
		if (vis[node]) continue;//用来去除同一个节点不同的dist，因为最小的dist在堆顶，所以不影响
		vis[node] = true;
		for (int i = h[node]; i != -1; i = ne[i])
		{
			if (dist[e[i]] > distance + W[i]) {
				dist[e[i]] = distance + W[i];
				heap.push({dist[e[i]],e[i]});
				//后面dist更小得会出现在堆的上面，被输出的优先级高与距离大的那次存储
			}
		}
	}
	return dist[n];
}
int main()
{
	memset(h, -1, sizeof h);
	memset(dist, 0x3f, sizeof dist);
	int m, x, y, w;
	cin >> n >> m;
	while (m--)
	{
		cin >> x >> y >> w;
		add(x, y, w);
	}
	int ret = Dijkstra();
	if (ret == 0x3f3f3f3f) cout << -1;
	else cout << ret;
	return 0;
}