Dijkstra 最短路径算法可视化教学

Dijkstra 算法：寻找最短之路

Dijkstra（迪杰斯特拉）算法是解决图论中单源最短路径问题的经典算法。它专门用于查找从图中的一个指定起始点（源点）到所有其他点的最短路径。

核心要求：该算法仅适用于所有边的权重（表示距离、成本或时间等）都是非负数的图。

图 (Graph): 由节点（顶点）和连接节点的边组成。
权重 (Weight): 赋予每条边的数值，代表通过该边的“代价”。
最短路径 (Shortest Path): 从源点到目标点总权重最小的路径。

关键点提示：强调“单源”和“非负权重”是 Dijkstra 算法的关键前提。可以类比现实生活中没有“负距离”或“负时间”。

算法应用：无处不在的最短路径

Dijkstra 算法因其高效和直观性，在众多领域都有广泛应用：

📍 地图导航： 计算两个地点间的最快或最短驾车路线（如 GPS 系统）。
🌐 网络路由： 在互联网中，路由器使用类似算法决定数据包传输的最佳路径（如 OSPF 协议）。
🤖 任务规划： 在机器人或游戏中，计算角色到达目标点的最优移动路径。
🔗 社交网络： 分析人与人之间的“最短联系链”。
✈️ 物流运输： 规划货物从仓库到客户的最优配送路线。

理解 Dijkstra 有助于我们认识到许多日常科技背后的智能决策原理。

关键点提示：结合具体例子解释“权重”可以代表不同含义（距离、时间、成本、网络延迟等），让学生理解算法的通用性。

核心思想：贪心与松弛

Dijkstra 算法采用贪心策略 (Greedy Strategy)，逐步构建最短路径树：

初始化： 将源点距离设为 0，其他所有点距离设为无穷大 (∞)。创建一个优先队列，包含所有节点。
选择最小： 从队列中选出当前距离源点最近的未访问节点 `u`。
松弛邻边 (Relaxation)： 对于 `u` 的每个邻居 `v`，检查是否可以通过 `u` 到达 `v` 获得更短的路径。即：如果 `dist[u] + weight(u, v) < dist[v]`，则更新 `dist[v]` 为更小的值，并记录 `u` 为 `v` 的前驱节点。
标记与重复： 将 `u` 标记为已访问（从队列移除），重复步骤 2-3，直到队列为空或找到目标节点。

“贪心”体现在每次都选择当前最优（距离最短）的节点，“松弛”是不断优化路径估计的过程。

关键点提示：解释“优先队列”的作用（快速找到最小距离节点）和“松弛”操作的含义（尝试用新路径更新距离）。这是算法效率和正确性的关键。

控制面板

参数设置

节点数量:

起始节点:

动画速度:

1.0x

请点击“生成示例图”开始。

节点	距离 (dist)	前驱 (prev)
请先生成图并运行算法

优先队列 (Priority Queue):

Dijkstra 算法 C++ 实现

▼

// Dijkstra 最短路径算法 C++ 实现 (使用优先队列优化)
#include <bits/stdc++.h>
using namespace std;

const int INF = numeric_limits::max(); // 定义无穷大
// 定义图的边
struct Edge {
    int to;      // 目标节点
    int weight;  // 边的权重
};

// 定义优先队列中的节点 (用于小顶堆)
struct Node {
    int id;      // 节点ID
    int dist;    // 从源点到此节点的当前估计距离

    // 重载大于号，用于优先队列（默认是大顶堆，我们需要小顶堆）
    bool operator>(const Node& other) const {
        return dist > other.dist;
    }
};

// Dijkstra 算法实现
// graph: 邻接表表示的图, n: 节点数量, source: 源点索引
// 返回: 从源点到各节点的最短距离 map
map<int, int> dijkstra(const vector>& graph, int n, int source, map<int, int>& prev) {
    // 初始化距离数组，所有距离设为无穷大
    map<int, int> dist;
    for (int i = 0; i < n; ++i) {
        dist[i] = INF;
        prev[i] = -1; // 初始化前驱为 -1 (表示没有前驱)
    }

    // 源点距离设为 0
    dist[source] = 0;

    // 定义优先队列（小顶堆）
    priority_queue, greater> pq;
    pq.push({source, 0}); // 将源点加入队列

    // 主循环，直到优先队列为空
    while (!pq.empty()) {
        // 取出当前距离最小的节点
        Node current = pq.top();
        pq.pop();

        int u = current.id;
        int d = current.dist;

        // 如果取出的距离大于已记录的距离，说明是旧的、无效的节点，跳过
        if (d > dist[u]) {
            continue;
        }

        // 遍历节点 u 的所有邻边，进行松弛操作
        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            // 松弛操作：如果通过 u 到达 v 的距离更短
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                // 更新距离和前驱
                dist[v] = dist[u] + weight;
                prev[v] = u;
                // 将更新后的节点加入优先队列
                pq.push({v, dist[v]});
            }
        }
    }

    return dist; // 返回从源点到所有节点的最短距离
}

// --- 主函数示例 (仅作展示，网页中不直接运行) ---
/*
int main() {
    int n = 6; // 节点数量 (0 to 5, 代表 A to F)
    vector> adj(n); // 邻接表

    // 添加边 (示例图, 无向图需要双向添加)
    auto add_edge = [&](int u, int v, int w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w}); // 如果是无向图
    };

    add_edge(0, 1, 7);  // A-B (7)
    add_edge(0, 2, 9);  // A-C (9)
    add_edge(0, 5, 14); // A-F (14)
    add_edge(1, 2, 10); // B-C (10)
    add_edge(1, 3, 15); // B-D (15)
    add_edge(2, 3, 11); // C-D (11)
    add_edge(2, 5, 2);  // C-F (2)
    add_edge(3, 4, 6);  // D-E (6)
    add_edge(4, 5, 9);  // E-F (9)

    int start_node = 0; // 选择源点 A (索引 0)
    map predecessors;
    map distances = dijkstra(adj, n, start_node, predecessors);

    cout << "从节点 " << (char)('A' + start_node) << " 出发的最短路径:\n";
    for (int i = 0; i < n; ++i) {
        cout << "到 " << (char)('A' + i) << ": ";
        if (distances[i] == INF) {
            cout << "不可达\n";
        } else {
            cout << distances[i] << " (前驱: ";
            if (predecessors[i] == -1) cout << "无";
            else cout << (char)('A' + predecessors[i]);
            cout << ")\n";
        }
    }

    return 0;
}
*/