Dijkstra算法是一种用于解决最短路径问题的图算法，由荷兰计算机科学家Edsger W. Dijkstra在1956年提出。它可以找到两个节点之间的最短路径，但仅适用于没有负权边的有向图或无向图。
Dijkstra算法的原理
1. 创建一个节点集合，用于存储已经确定最短路径的节点，将起始节点添加到该集合中。
2. 初始化一个距离集合，用于存储起始节点到其他节点的距离。起始节点的距离为0，其他节点的距离初值为正无穷。
3. 当节点集合不为空时，重复以下步骤：
- 从距离集合中选取一个距离最小的节点，将其从距离集合中删除，并加入节点集合。
- 对于该节点的每个邻居节点，计算从起始节点经过当前节点到达邻居节点的距离。如果该距离小于目前距离集合中的距离，则更新距离集合中的距离。
4. 当节点集合为空时，算法结束。此时，距离集合中存储的距离即为最短路径的结果。
通过这种方式，Dijkstra算法能够确定起始节点到其他节点的最短路径，并计算出每个节点的最短距离。这种算法的时间复杂度为O(V^2)，其中V是节点数。
Dijkstra算法的核心思想
Dijkstra算法的核心思想是通过每一轮迭代，不断确定起始节点到当前节点的最短路径，并更新每个节点的最短距离。同时，通过选取距离最小的节点，保证每一轮加入节点集合的节点都是距离起始节点最近的节点。
使用一个优先级队列（如最小堆）来选择距离集合中距离最小的节点，可以提高算法的效率。每次从优先级队列中取出距离最小的节点，将其加入节点集合，并更新与该节点直接相连的节点的最短距离。这样，就可以在O(logV)的时间内选取距离最小的节点，从而将Dijkstra算法的时间复杂度优化为O((V+E)logV)，其中E是边的数量。
总结起来，Dijkstra算法通过不断选取距离最小的节点，逐步确定起始节点到其他节点的最短路径，并计算出每个节点的最短距离。这使得Dijkstra算法成为一种常用且有效的最短路径算法，广泛应用于网络路由、地图导航等领域。
Dijkstra算法的关键在于不断更新节点的最短距离，并选择最小的距离进行扩展，直到所有节点都被加入节点集合为止。这样就能保证每个节点被访问时，它的最短距离已经被确定下来。
需要注意的是，Dijkstra算法要求图中没有负权边。因为它利用了每次扩展节点时的最小距离，如果存在负权边，可能会导致出现环路，破坏了最短路径的定义。
最后，通过将前驱节点集合中记录的路径逆序输出，我们可以得到从起始节点到目标节点的最短路径。
总结来说，Dijkstra算法通过不断选择距离最小的节点，并更新节点距离及前驱节点，来找到起始节点到其他节点的最短路径。它是一种广泛使用的最短路径算法，但要求图中没有负权边。在实际应用中，可以利用优先级队列来提高算法的效率。
在实际应用中，Dijkstra算法还可以扩展为解决单源最短路径问题和全源最短路径问题。
对于单源最短路径问题，即给定一个起始节点，需要计算出该节点到图中所有其他节点的最短路径。在使用Dijkstra算法解决单源最短路径问题时，只需将起始节点到其他节点的距离初始化为正无穷，然后进行Dijkstra算法的步骤即可。
而对于全源最短路径问题，即给定图中所有节点，需要计算出任意两个节点之间的最短路径。在使用Dijkstra算法解决全源最短路径问题时，需要对每个节点都执行一次Dijkstra算法，分别得到该节点到其他节点的最短路径。
需要注意的是，在面对大规模图和较多节点时，Dijkstra算法可能会变得低效，因为它需要计算每个节点到所有其他节点的最短路径。在这种情况下，可以考虑使用其他最短路径算法，如A*算法、Bellman-Ford算法或Floyd-Warshall算法，来提高计算效率。
总结来说，Dijkstra算法是一种解决最短路径问题的图算法，通过不断选择距离最小的节点，并更新最短路径和前驱节点，来找到起始节点到其他节点的最短路径。它可用于解决单源最短路径问题和全源最短路径问题，但要求图中没有负权边。在实际应用中，可以根据具体需求选择合适的最短路径算法。
例子
#include <iostream> #include <vector> #include <queue> #include <limits> using namespace std; // 定义无穷大表示不可达 const int INF = numeric_limits<int>::max(); // 图的邻接表表示 typedef pair<int, int> Edge; // <邻居节点, 边权重> typedef vector<vector<Edge>> Graph; // 邻接表表示的图 vector<int> Dijkstra(const Graph& graph, int start) { int n = graph.size(); // 图中节点的个数 vector<int> dist(n, INF); // 用于存储起始节点到各个节点的最短距离 dist[start] = 0; // 起始节点到自身的距离为0 // 定义优先队列，按照节点到起始节点的最短距离排序 priority_queue<Edge, vector<Edge>, greater<Edge>> pq; pq.push({0, start}); while (!pq.empty()) { int u = pq.top().second; // 当前最短路径节点 int d = pq.top().first; // 当前最短路径值 pq.pop(); // 如果当前节点已经被访问过，则跳过 if (d > dist[u]) { continue; } // 遍历当前节点的邻居节点 for (const Edge& edge : graph[u]) { int v = edge.first; // 邻居节点 int weight = edge.second; // 边权重 // 如果经过当前节点到达邻居节点的距离更短，则更新最短距离并加入队列 if (dist[u] + weight < dist[v]) { dist[v] = dist[u] + weight; pq.push({dist[v], v}); } } } return dist; } int main() { int n = 5; // 图中节点的个数 Graph graph(n); // 创建一个空的图 // 添加边和边权重 graph[0].push_back({1, 4}); graph[0].push_back({2, 1}); graph[1].push_back({4, 4}); graph[1].push_back({3, 1}); graph[2].push_back({1, 2}); graph[2].push_back({3, 5}); graph[3].push_back({4, 3}); int start = 0; // 起始节点 // 运行Dijkstra算法，计算起始节点到所有其他节点的最短距离 vector<int> shortestDist = Dijkstra(graph, start); // 输出结果 cout << "Shortest distances from node " << start << " to all other nodes:\n"; for (int i = 0; i < n; ++i) { cout << "Node " << i << ": " << shortestDist[i] << endl; } return 0; }
