【图论】迪杰特斯拉算法

用户11305458

发布于 2024-10-09 17:31:36

1540

发布于 2024-10-09 17:31:36

文章被收录于专栏：学习

迪杰特斯拉算法

迪杰特斯拉算法是由荷兰计算机科学家艾兹赫尔·迪杰特斯拉（Edsger W. Dijkstra）在1956年提出的，用于解决单源最短路径问题的经典算法。该算法的目标是从一个起始顶点找到到图中其他顶点的最短路径。

主要特点

适用于带权图，其中权重为非负数。（为什么只适用于非负数，因为迪杰斯特拉的思想是贪心测量，当有负权引入的时候，贪心策略将不再适用）
解决从单个源点到其他所有顶点的最短路径问题。
时间复杂度：当使用优先队列（例如堆）时，复杂度为

O(E \log V)

，其中

为顶点数量，

为边的数量。

基本思想

Dijkstra算法通过不断探索距离最近的顶点，逐步扩展其最短路径的已知范围，直到找到从源点到所有其他顶点的最短路径。该算法基于贪心策略：每一步选择尚未处理的、距离源点最近的顶点进行扩展。

算法步骤

初始化：
- 将起始顶点的距离设为0，其余所有顶点的距离设为∞（表示不可达）。
- 使用一个优先队列（或最小堆）来存储顶点及其当前的最短距离。
取距离源点最近的顶点，并标记为已处理。
对于该顶点的每个邻接顶点，更新其最短距离（如果通过当前顶点可以获得更短的路径，则更新距离）。
重复步骤2和3，直到所有顶点都被处理过，或优先队列为空。

示例

实现迪杰斯特拉算法

基本步骤

首先假设我们有如下的一个图：

灰色的点代表起点，我们需要从起点开始算每个点到起点的最短路径。第一步按照迪杰斯特拉的表述应该将起点到起点的最短路径初始化为0，起点到另外其他点的距离初始化为正无穷。

这里我们更新完s点之后，应该更新和s点相连的点的最短路径了，由于之前s到t点和到y点的最短路径是正无穷，由于st和sy都小于两个最短路径，所以更新两个最短路径。

根据贪心策略，更新出来的两个最短路径，sy更小，所以我们应该更新y相连的路径。

所以接下来我们应该更新y连接的点的最短路径。

由于原本s到t的最短路径是10，但是现在的最短路径更新了之后是8，所以更新结果，由于之前s到x的最短路径是正无穷，所以现在将最短路径更新为14，s到z 也是相同的，因为之前的最短路径是正无穷，所以现在将最短路径更新为7. 在这三条最短路径中选择最短的那条：

这里就应该以z为新的起点

更新z连接的顶点，z一共有两条边，一条是zs，一条是zx，由于s到s是最近的0，所以这里不需要更新，由于之前s到x的距离是14，所以这里更新s到x的距离。接下来再从剩下的边中，选择最小的路径。

从t点开始只有一条路径，所以这里t到x，tx是1，由于之前的st的最短路径是8，所以此时的最短路径是9,9<13所以这里应该更新最短路径为9

这里最短路径算是更新完了。

算法思路

由于这里我们涉及到最短路径，所以应该开辟一个dist数组，我们来想一想一个dist数组是否能解决问题，很显然是不能的，我们还需要一个数组，记录当前最短路径的前一个顶点的下标，在遍历的时候我们可以索引每一个顶点了。 代码展示：

void Dijkstra(const V& src, vector<W>& dist, vector<int>& pPath)
{
	//获取起点的下标
	size_t srci = GetVertexIndex(src);
	//确定节点的数量
	size_t n = _vertexs.size();
	dist.resize(n, MAX_W);
	pPath.resize(n, MAX_W);

	//自己到自己的距离是0
	dist[srci] = 0;
	//自己的前一个是自己
	pPath[srci] = srci;
	//已经确定最短路径的顶点的集合
	vector<bool> S(n, false);
	for(size_t j=0;j<n;j++)
	{
		//选择最短路径顶点且不在s中更新其他路径
		int u = 0;     //最小的那个点
		W min = MAX_W; //最小权值
		for (size_t i = 0;i < n;i++)
		{
			if (S[i] == false && dist[i] < min)
			{
				//选出最小的点
				u = i;
				//更新最小权值
				min = dist[i];
			}
		}

		//u被选出来
		S[u] = true;
		//松弛更新u连接出去的顶点v    srci->u   u->v
		for (size_t v = 0;v < n;v++)
		{
			//确定u连接出去的所有边
			if (S[v] == false && _matrix[u][v] != MAX_W && (dist[u] + _matrix[u][v]) < dist[v])
			{
				dist[v] = dist[u] + _matrix[u][v];
				//将v的父亲更新为u
				pPath[v] = u;
			}
		}
	}
}

打印路径节点和最短路径：

//打印最短路径
void PrinrtShotPath(const V& src, vector<W>& dist, vector<int>& pPath)
{
	//获取起点的下标
	size_t srci = GetVertexIndex(src);
	//确定节点的数量
	size_t n = _vertexs.size();
	for (size_t i = 0;i < n;i++)
	{
		if (i != srci)
		{
			// 先找出i顶点的路径
			vector<int> path;
			size_t parenti = i;
			//先将自己存进去(自己不是原点先push进去）
			while (parenti != srci)
			{
				path.push_back(parenti);
				parenti = pPath[parenti];
			}
			path.push_back(srci);
			//将路径逆置
			reverse(path.begin(), path.end());
			//打印出路径
			for (auto e : path)
			{
				cout << _vertexs[e] << "->";
			}
			//打印最短路径
			cout << dist[i];
			cout << endl;
		}
	}
}

因为根据最后一个节点去推上一个节点，推完之后数组中的节点会是一个反着的路径，所以在打印的时候，应该先把数组逆置，逆置之后再进行打印。