Dijkstra算法详解：从基本原理到代码实现
Dijkstra算法详解：从基本原理到代码实现
Dijkstra算法是计算机科学领域中用于解决最短路径问题的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉于1959年提出。该算法在多个领域都有广泛的应用，包括网络路由、无线传感器网络、地理信息系统以及机器人导航等。本文将从算法的基本思想、实现步骤到具体的代码实现，全面解析Dijkstra算法的核心原理和应用场景。
1. 前言
迪杰斯特拉算法（Dijkstra）是由荷兰计算机科学家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法。主要用于求解从一个源节点到其他所有节点的最短路径问题，解决的是有权图中最短路径问题。Dijkstra算法应用十分广泛。在网络路由上，路由协议（如OSPF和IS-IS）中，Dijkstra算法用于计算网络中的最短路径，从而确定数据包的转发路径。在无线传感器网络或移动自组织网络中，Dijkstra算法可以帮助寻找最低能耗路径或最可靠的通信路径。在地理信息系统（GIS）方面，导航系统：如Google Maps、百度地图、高德地图和GPS设备，使用Dijkstra算法来计算最短路径，以提供最佳驾驶或步行路线。在路径规划方面，机器人导航中，Dijkstra算法用于计算机器人在环境中的最短路径，避免障碍物并到达目标位置等等。
2. 算法思想
如图2.1所示，是一张图，边上的值表示表示权重，在不同的应用中权重可表示不同的意思。下面我以这一张图来简介算法步骤。设G=(V,E)是一个带权有向图，把图中节点集合V分成两组，第一组为已求出最短路径的节点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将该节点加入到集合S中，直到全部节点都加入到S中，算法就结束了）；第二组为其余未确定最短路径的节点集合（用U表示），按最短路径长度的递增次序依次把第二组的节点加入S中。在加入的过程中，总保持从源点v到S中各节点的最短路径长度不大于从源点v到U中任何节点的最短路径长度。 此外，每个节点对应一个距离，S中的节点的距离就是从v到此节点的最短路径长度，U中的节点的距离，是从v到此节点只包括S中的节点为中间节点的当前最短路径长度。
从D节点开始，把D节点加入S集合，其余的还是在U集合中，D节点的邻居有C，E节点，计算距离，其他节点没有相邻故是无穷大。3小于4,故将C加入S集合中。此时B，F也相邻，计算出距离。由于D-C-E的距离8是大于D-E距离4的，故D-E的距离不更新。下一次离集合S最近的点是E，把E加入S集合，由于D-E-F距离6小于DCF距离9，故更新D到F的值。如图所以，一直到集合U中的元素为0。节点D到各个节点的最短距离就被找了出来。
3. 代码实现
Python代码实现
import heapq
def dijkstra(graph, start):
# 初始化距离字典，将起始节点的距离设为0，其他节点设为无穷大
distances = {node: float('infinity') for node in graph}
distances[start] = 0
# 初始化一个最小堆来存储节点和距离，以便能够按距离提取最小节点
priority_queue = [(0, start)]
# 当优先队列不为空时，继续执行
while priority_queue:
# 提取距离最小的节点
current_distance, current_node = heapq.heappop(priority_queue)
# 如果当前节点的距离已经大于优先队列中记录的距离，则跳过
if current_distance > distances[current_node]:
continue
# 遍历当前节点的所有邻居
for neighbor, weight in graph[current_node].items():
# 计算通过当前节点到达邻居节点的距离
distance = current_distance + weight
# 如果找到一条更短的路径，则更新距离并添加/更新邻居节点到优先队列
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 示例图（使用邻接列表表示）
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
# 使用 Dijkstra's 算法从节点 'A' 开始计算最短路径
print(dijkstra(graph, 'A')) # 输出: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
C++代码实现
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <unordered_map>
using namespace std;
// 使用pair作为优先队列的元素，其中first是距离，second是节点
typedef pair<int, int> PII;
// Dijkstra算法
vector<int> dijkstra(const vector<vector<pair<int, int>>>& graph, int start) {
int num_nodes = graph.size();
vector<int> distances(num_nodes, INT_MAX); // 初始化所有节点的距离为无穷大
distances[start] = 0; // 源节点的距离为0
// 优先队列用于存储待处理的节点，按照距离从小到大排序
priority_queue<PII, vector<PII>, greater<PII>> pq;
pq.push({0, start}); // 将源节点入队
while (!pq.empty()) {
int curr_dist = pq.top().first; // 当前距离
int curr_node = pq.top().second; // 当前节点
pq.pop();
// 如果当前节点的距离已经被更新过，则跳过
if (curr_dist > distances[curr_node]) continue;
// 遍历当前节点的所有邻居
for (const auto& neighbor : graph[curr_node]) {
int next_node = neighbor.first;
int weight = neighbor.second;
// 计算通过当前节点到达下一个节点的距离
int new_dist = curr_dist + weight;
// 如果找到了一条更短的路径，则更新距离
if (new_dist < distances[next_node]) {
distances[next_node] = new_dist;
pq.push({new_dist, next_node}); // 将下一个节点入队
}
}
}
return distances;
}
int main() {
// 示例图（使用邻接列表表示）
vector<vector<pair<int, int>>> graph = {
{{1, 4}, {0, 1}}, // A连接到B和C，距离分别为1和4
{{0, 1}, {1, 2}, {2, 5}}, // B连接到A、C和D，距离分别为1、2和5
{{0, 4}, {1, 2}, {3, 1}}, // C连接到A、B和D，距离分别为4、2和1
{{2, 5}, {3, 1}} // D连接到B和C，距离分别为5和1
};
// 假设节点从0开始编号（A为0，B为1，依此类推）
int start_node = 0; // 从A节点开始
// 使用Dijkstra算法计算最短路径
vector<int> distances = dijkstra(graph, start_node);
// 输出结果
for (int i = 0; i < distances.size(); ++i) {
cout << "Distance from node " << start_node << " to node " << i << ": " << distances[i] << endl;
}
return 0;
}