Dijkstra-学习笔记

Dijkstra算法是一种用于寻找图中两点之间最短路径的算法。它由荷兰计算机科学家艾兹赫尔·戴克斯特拉（Edsger W. Dijkstra）在1956年提出，并于1959年发表。

算法原理

Dijkstra算法适用于带权重的图，包括有向图和无向图。算法的核心思想是贪心法：每次找到距离起点最近的一个未被访问的顶点，然后考察所有由这个顶点引出的边，通过这个顶点更新起点到其他所有顶点的距离。

算法步骤

1. 初始化：将所有顶点标记为未访问，设置起点到自身的最短距离为 \(0\)，到其他所有顶点的最短距离为无穷大。
2. 选择最小距离的未访问顶点 \(u\)，访问并标记该顶点。
3. 更新顶点 \(u\) 的邻接顶点的距离。
4. 重复步骤2和3，直到所有顶点都被访问。

C++实现

下面是Dijkstra算法的一个基本C++实现示例：

#include <iostream>
#include <vector>
#include <limits>
#include <set>
using namespace std;
void Dijkstra(const vector<vector<pair<int, int>>>& graph, int src) {
	int V = graph.size();
	vector<int> dist(V, numeric_limits<int>::max());
	set<pair<int, int>> setds;
	dist[src] = 0;
	setds.insert(make_pair(0, src));
	while (!setds.empty()) {
		pair<int, int> tmp = (setds.begin());
		setds.erase(setds.begin());
		int u = tmp.second;
		for (auto i = graph[u].begin(); i != graph[u].end(); ++i) {
			int v = (i).first;
			int weight = (i).second;
			if (dist[v] > dist[u] + weight) {
				if (dist[v] != numeric_limits<int>::max()) {
					setds.erase(setds.find(make_pair(dist[v], v)));
				}
				dist[v] = dist[u] + weight;
				setds.insert(make_pair(dist[v], v));
			}
		}
	}
	cout << "Vertex Distance from Source\n";
	for (int i = 0; i < V; ++i) cout << i << "\t\t" << dist[i] << endl;
}
int main() { // 示例图的邻接表表示
	vector<vector<pair<int, int>>> graph = { {{1, 4}, {2, 1}}, {{2, 3}, {3, 2}, {4, 3}}, {{1, 1}, {3, 4}, {4, 5}}, {{4, 1}}, {} };
	Dijkstra(graph, 0);
	return 0;
}

注意事项

• Dijkstra算法不能处理图中含有负权边的情况。如果图中含有负权边，可以考虑使用Bellman-Ford算法。
• 上述C++实现使用了std::set来寻找当前未访问顶点中距离最小的顶点，这使得算法的时间复杂度为 \(O(V^2)\)。对于稠密图来说是可接受的，但对于稀疏图，可以使用优先队列（如std::priority_queue）来优化，将时间复杂度降低到 \(O((V+E)log_2V)\)。

结论

Dijkstra算法是图论中一个非常基础且重要的算法，适用于解决许多实际问题，如网络路由、地图导航等。掌握其原理和实现于解决许多实际问题，如网络路由、地图导航等。掌握其原理和实现对于学习更高级的图论算法也非常有帮助。

扩展阅读

• 优化技巧：在实际应用中，Dijkstra算法的性能可以通过使用优先队列来大幅度提升。优先队列能够保证每次从队列中取出的都是当前最短距离的顶点，这样可以避免对所有顶点的遍历，从而降低算法的时间复杂度。
• 变体：Dijkstra算法有许多变体，例如，当需要找到从源点到所有其他顶点的最短路径时，可以稍微修改算法来实现。此外，对于特定类型的图（如非负权重图），Dijkstra算法尤其有效。
• 实际应用：在实际应用中，如地图软件的路径规划，通常会结合Dijkstra算法和其他技术（如A*搜索算法）来提高效率和准确性。

结语

Dijkstra算法是图论中的经典算法之一，它简洁而强大。通过本篇学习笔记，你应该对Dijkstra算法有了基本的了解和掌握。实际编程时，建议多做练习，尝试在不同的图结构上应用Dijkstra算法，以加深理解和熟练度。