Dijkstra单源最短路朴素算法（空间优化）

Dijkstra单源最短路朴素算法（空间优化）

基于使用邻接表存储连接边的方法，可以有效的降低空间复杂度

在稀疏图（边的数量远小于顶点数量平方的图）中，邻接矩阵会大量占用无用的内存，导致Re，我们采用邻接表的办法，只存储存在的边，减少无关占用。相反，在稠密图（边的数量接近顶点数的平方的图）中，邻接表会遍历一整条链，检索时间会大大增加（不做优化），我们就采取邻接矩阵的方法来存储，每次只需要通过下标快速检索

通过结构体和vector来构造边的链表

struct edge
{
	int v, w;//v表示连接到的节点，w表示边权重
};
vector<edge> e[10010];

插入边操作

void insert(int u, int v, int w) {
	e[u].push_back({ v,w });
}

cin >> u >> v >> w;
insert(u, v, w);

然后是使用朴素的Dijkstra算法实现单源最短路

void dijkstra(int s) {
	memset(dis, 0x3f, sizeof dis);//初始化可以使用memset 0x3f 批量操作
	dis[s] = 0;//起始点被访问
	for (int i = 1; i <= n; i++) {
		int min_node = 0;//初始化

		for (int j = 1; j <= n; j++)//遍历所有点
			min_node = dis[j] < dis[min_node] && !vis[j] ? j : min_node;
//找未被访问过的点中的最近点，判断最小值
		
		if (!min_node) break;//如果没能找到，即min_node未更新，退出循环
		vis[min_node] = 1;//当前点已被访问过

		for (auto it = e[min_node].begin(); it != e[min_node].end(); it++)//迭代器遍历当前点的所有连通边
			dis[it->v] = min(dis[min_node] + it->w, dis[it->v]);//更新最小值
	}
}

使用迭代器遍历时，需要通过箭头运算符 -> 来访问结构体的成员元素

for (auto it = e[min_node].begin(); it != e[min_node].end(); it++)
	dis[it->v] = min(dis[min_node] + it->w, dis[it->v]);

同样也可使用C++11标准内的区间遍历

for (auto iter : e[min_node])
	dis[iter.v] = min(dis[min_node] + iter.w, dis[iter.v]);

区间遍历的一般格式

for (dataType rangeVariable : array) 

dataType为需要遍历的数组的数据类型， rangeVariable为循环内范围变量的名称，该变量用来接收遍历元素的值，array为需要遍历的数组名，区间遍历的范围变量只需要通过 . 就能访问结构的成员元素