【数据结构与算法-Day 46】图解最短路径：Dijkstra算法从原理到实战（无负权边）

大模型铲屎官

1213人浏览 · 2026-01-01 22:03:17

大模型铲屎官 · 2026-01-01 22:03:17 发布

Langchain系列文章目录

01-玩转LangChain：从模型调用到Prompt模板与输出解析的完整指南
 02-玩转 LangChain Memory 模块：四种记忆类型详解及应用场景全覆盖
 03-全面掌握 LangChain：从核心链条构建到动态任务分配的实战指南
 04-玩转 LangChain：从文档加载到高效问答系统构建的全程实战
 05-玩转 LangChain：深度评估问答系统的三种高效方法（示例生成、手动评估与LLM辅助评估）
06-从 0 到 1 掌握 LangChain Agents：自定义工具 + LLM 打造智能工作流！
07-【深度解析】从GPT-1到GPT-4：ChatGPT背后的核心原理全揭秘
 08-【万字长文】MCP深度解析：打通AI与世界的“USB-C”，模型上下文协议原理、实践与未来

数据结构与算法系列文章目录

文章目录

Langchain系列文章目录
Python系列文章目录
PyTorch系列文章目录
机器学习系列文章目录
深度学习系列文章目录
Java系列文章目录
JavaScript系列文章目录
Python系列文章目录
Go语言系列文章目录
Docker系列文章目录
数据结构与算法系列文章目录
摘要
一、引言：最短路径问题是什么？
- 1.1 生活中的最短路径
- 1.2 问题的形式化定义
二、Dijkstra 算法的核心思想：贪心的智慧
- 2.1 算法的直观理解
- 2.2 核心三要素
三、算法执行步骤详解
- 3.1 初始化
- 3.2 迭代过程（循环 V 次）
- 3.3 流程图可视化
四、Dijkstra 算法的实例演练
- 4.1 示例图
- 4.2 分步图解
五、代码实现：从朴素到优化
- 5.1 基于邻接矩阵的实现 ( $O(V^2)$ )
- 5.2 基于优先队列（堆）的优化 ( $\log V)$ )
六、Dijkstra 算法的局限性
- 6.1 致命弱点：无法处理负权边
七、应用场景
八、总结

摘要

在纷繁复杂的网络世界中，如何找到从一个点到另一个点的最短路径，是计算机科学领域一个经典且至关重要的问题。无论是GPS导航规划最快路线，还是网络路由器选择最高效的数据传输路径，其背后都离不开最短路径算法的支持。本文将深入探讨解决单源最短路径问题的经典算法——Dijkstra（迪杰斯特拉）算法。我们将从其核心的贪心思想出发，通过生动的图解和实例演练，逐步揭示其工作原理。此外，文章还将提供从朴素实现到优先队列优化的两种核心代码实现（C++/Java），并分析其性能差异，最后探讨其适用场景与局限性。无论你是算法初学者还是希望巩固知识的进阶者，本文都将为你构建一个关于Dijkstra算法的清晰知识体系。

一、引言：最短路径问题是什么？

在正式进入算法学习之前，我们首先需要明确我们要解决的问题是什么。

1.1 生活中的最短路径

想象一下，你正计划一场自驾游，从“城市A”出发，希望到达“城市D”。途中有多个城市可以中转，每两个城市之间的道路都有不同的距离。你手上的地图就是一个“图”，城市是“顶点”，道路是“边”，道路的长度就是“权重”。你的目标就是找到一条从A到D的总距离最短的路线。

这就是一个典型的最短路径问题。它不仅仅局限于地理距离，也可以是时间、费用、或者网络延迟等任何可以量化的成本。

1.2 问题的形式化定义

在计算机科学中，我们将这个问题进行抽象和形式化：

图 (Graph)：一个图由顶点集合 $V$ 和边集合 $E$ 构成，记为 $G = (V, E)$ 。
带权图 (Weighted Graph)：图中的每条边 $(u, v)$ 都关联一个数值，称为权重 $w (u, v)$ ，代表从顶点 $u$ 到顶点 $v$ 的成本。
路径 (Path)：从一个顶点到另一个顶点经过的边序列。
路径长度 (Path Length)：一条路径上所有边的权重之和。
单源最短路径 (Single-Source Shortest Path, SSSP)：给定一个图 $G$ 和一个源顶点 $s$ ，找出从 $s$ 到图中所有其他顶点的最短路径。

Dijkstra算法正是解决带权有向图或无向图中，边权为非负数时的单源最短路径问题的利器。

二、Dijkstra 算法的核心思想：贪心的智慧

Dijkstra算法由荷兰计算机科学家艾兹赫尔·迪杰斯特拉在1956年提出，其核心是一种贪心策略 (Greedy Strategy)。

2.1 算法的直观理解

我们可以用一个“感染”模型来直观理解Dijkstra算法。

初始状态：只有源顶点 $s$ 是“已确定最短路径”的（可以看作是第一个“感染者”），它到自身的距离为0。其他所有顶点都处于“未确定”状态，距离源点的距离被初始化为无穷大。
扩张过程：算法每次都从“未确定”的顶点中，选择一个距离源顶点 $s$ 最近的顶点 $u$ 。
确定与更新：一旦选择了顶点 $u$ ，我们就贪心地认为：从源点 $s$ 到 $u$ 的当前最短路径，就是最终的最短路径了。因此，将 $u$ 标记为“已确定”。然后，通过 $u$ 这个新确定的“跳板”，去看看能否找到到达 $u$ 的邻居们更近的路径，这个过程称为“松弛”。
循环往复：重复第2、3步，直到所有顶点都被标记为“已确定”，或者所有从源点可达的顶点都已处理完毕。

这个过程就像一个以源点为中心的不断扩大的圈，每次都将离中心最近的点纳入圈内，并更新圈外邻近点的信息。

2.2 核心三要素

为了实现上述思想，我们需要三个关键的数据结构：

2.2.1 `dist` 数组：距离记录本

一个数组（或哈希表），dist[v] 记录了从源顶点 $s$ 到顶点 $v$ 的当前已知的最短路径长度。

初始化：dist[s] = 0，对于所有其他顶点 $\ne s$ ，dist[v] = \infty。
更新：在算法执行过程中，dist 数组的值会不断被优化，变得越来越小，直到最终确定。

2.2.2 `visited` 集合：已确定最短路径的顶点

一个集合（通常用布尔数组实现），visited[v] 用于标记顶点 $v$ 是否已经找到了从源点 $s$ 出发的最短路径。

初始化：所有顶点都未被访问，visited 集合为空。
操作：每次从dist数组中选出值最小且未被访问的顶点后，就将其加入 visited 集合。

2.2.3 松弛 (Relaxation) 操作：更新最短路径

这是算法的核心操作。当我们考察一个新确定的顶点 $u$ 和它的一个邻居 $v$ 时，我们会检查是否存在一条更短的路径：源点 $s$ -> … -> $u$ -> $v$ 。
如果 dist[u] (从 $s$ 到 $u$ 的已知最短距离) 加上边 $(u, v)$ 的权重 $w (u, v)$ ，小于 dist[v] (从 $s$ 到 $v$ 的已知最短距离)，那么我们就找到了到达 $v$ 的一条更短路径。

其伪代码可以表示为：

if dist[u] + weight(u, v) < dist[v] then
    dist[v] = dist[u] + weight(u, v)

这个判断和更新的过程就叫做松弛。

三、算法执行步骤详解

现在，我们将上述思想和要素整合成一个清晰的算法流程。

3.1 初始化

创建一个 dist 数组，将源顶点 s 的距离 dist[s] 初始化为 0，其他所有顶点的距离初始化为无穷大 ( $\infty$ )。
创建一个 visited 布尔数组，所有元素初始化为 false。

3.2 迭代过程（循环 V 次）

对于一个包含 V 个顶点的图，循环 V 次：

3.2.1 选点：选择 `dist` 值最小的未访问顶点 `u`

在所有 visited[i] 为 false 的顶点中，找到一个使 dist[i] 最小的顶点，记为 u。

3.2.2 标记：将 `u` 加入 `visited` 集合

将 u 标记为已访问，即 visited[u] = true。这代表源点到 u 的最短路径已经被找到，就是 dist[u]。

3.2.3 松弛：更新 `u` 的所有邻接点

遍历 u 的所有邻接顶点 v：

如果 v 尚未被访问 (visited[v] == false)，并且通过 u 到达 v 的路径更短（即 dist[u] + w(u, v) < dist[v]），则执行松弛操作，更新 dist[v] = dist[u] + w(u, v)。

3.3 流程图可视化

下面是 Dijkstra 算法的执行流程图：

 渲染错误: Mermaid 渲染失败: Parse error on line 3: ... B --> C{循环 V 次 (V 为顶点数)}; C --> ----------------------^ Expecting 'SQE', 'DOUBLECIRCLEEND', 'PE', '-)', 'STADIUMEND', 'SUBROUTINEEND', 'PIPE', 'CYLINDEREND', 'DIAMOND_STOP', 'TAGEND', 'TRAPEND', 'INVTRAPEND', 'UNICODE_TEXT', 'TEXT', 'TAGSTART', got 'PS'

四、Dijkstra 算法的实例演练

纸上得来终觉浅，我们通过一个具体的例子来走一遍Dijkstra的完整流程。

4.1 示例图

假设我们有以下带权有向图，并选择顶点 0 作为源点。

4.2 分步图解

初始状态:

dist = [0, $\infty$ , $\infty$ , $\infty$ , $\infty$ ]
visited = [F, F, F, F, F] (T=True, F=False)

迭代次数	`visited` 集合	选择的顶点 u	`dist` 数组状态	描述
-	`{}`	-	`[0, inf, inf, inf, inf]`	初始化。源点0到自身距离为0。
1	`{}`	0 (dist=0)	`[0, 10, 3, inf, inf]`	选择`dist`最小的未访问顶点0。标记为已访问。松弛邻居1和2：`dist[1]=10`, `dist[2]=3`。
2	`{0}`	2 (dist=3)	`[0, 7, 3, 11, 5]`	在未访问的`{1,2,3,4}`中，2的`dist`最小(3)。标记2。松弛其邻居1,3,4：`dist[0]+d(0,2)+d(2,1)=3+4=7 < 10` -> `dist[1]=7`。`d(0,2)+d(2,3)=3+8=11` -> `dist[3]=11`。`d(0,2)+d(2,4)=3+2=5` -> `dist[4]=5`。
3	`{0, 2}`	4 (dist=5)	`[0, 7, 3, 11, 5]`	在`{1,3,4}`中，4的`dist`最小(5)。标记4。4没有未访问的邻居，不进行松弛。
4	`{0, 2, 4}`	1 (dist=7)	`[0, 7, 3, 8, 5]`	在`{1,3}`中，1的`dist`最小(7)。标记1。松弛其邻居3：`dist[1]+d(1,3)=7+1=8 < 11` -> `dist[3]=8`。
5	`{0, 2, 4, 1}`	3 (dist=8)	`[0, 7, 3, 8, 5]`	只剩3未访问，选择3。标记3。其邻居4已访问，不进行松弛。

最终结果:
算法结束。dist 数组为 [0, 7, 3, 8, 5]，这代表从源点0到各顶点的最短路径长度分别为：

0 -> 0: 0
0 -> 1: 7 (路径 0 -> 2 -> 1)
0 -> 2: 3 (路径 0 -> 2)
0 -> 3: 8 (路径 0 -> 2 -> 1 -> 3)
0 -> 4: 5 (路径 0 -> 2 -> 4)

五、代码实现：从朴素到优化

下面我们提供两种主流的Dijkstra算法实现。

5.1 基于邻接矩阵的实现 ( $O(V^2)$ )

这种实现方式直观，易于理解，但效率较低，适用于稠密图（边数 E 接近 $V^2$ ）。

5.1.1 复杂度分析

时间复杂度: 外层有一个 V 次的循环。内层循环为了找到 dist 最小的未访问顶点，需要遍历所有 V 个顶点，这耗时 $O (V)$ 。松弛操作总共会对每条边操作一次，在邻接矩阵中，这部分嵌套在两层循环内。总的时间复杂度是 $O(V^2)$ 。
空间复杂度: 需要一个邻接矩阵存储图 $O(V^2)$ ，以及 dist 和 visited 数组 $O (V)$ 。总空间复杂度为 $O(V^2)$ 。

5.1.2 C++ 代码实现

#include <iostream>
#include <vector>
#include <climits>

#define V 5 // 顶点数量
#define INF INT_MAX

// 寻找dist数组中未访问过的最小值的顶点索引
int minDistance(const std::vector<int>& dist, const std::vector<bool>& visited) {
    int min = INF, min_index = -1;
    for (int v = 0; v < V; ++v) {
        if (!visited[v] && dist[v] <= min) {
            min = dist[v];
            min_index = v;
        }
    }
    return min_index;
}

void dijkstra(int graph[V][V], int src) {
    std::vector<int> dist(V, INF);
    std::vector<bool> visited(V, false);

    dist[src] = 0; // 源点到自身距离为0

    // 对所有顶点进行操作
    for (int count = 0; count < V - 1; ++count) {
        // 1. 选点：选择当前dist最小的未访问顶点
        int u = minDistance(dist, visited);
        if (u == -1) break; // 所有可达顶点都已处理

        // 2. 标记：将选出的顶点标记为已访问
        visited[u] = true;

        // 3. 松弛：更新u的邻接点的dist值
        for (int v = 0; v < V; ++v) {
            // 条件：v未被访问，u-v有边，且通过u到v的路径更短
            if (!visited[v] && graph[u][v] && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }

    // 打印结果
    std::cout << "Vertex\tDistance from Source" << std::endl;
    for (int i = 0; i < V; ++i) {
        std::cout << i << "\t\t" << (dist[i] == INF ? "INF" : std::to_string(dist[i])) << std::endl;
    }
}

int main() {
    int graph[V][V] = {
        {0, 10, 3, 0, 0},
        {0, 0, 8, 1, 0},
        {0, 4, 0, 8, 2},
        {0, 0, 0, 0, 5},
        {0, 0, 0, 0, 0}
    };
    // 为了表示无穷，0表示无直连边，实际使用时需要区分0权重和无边
    // 这里的graph[u][v]=0代表无直连边

    dijkstra(graph, 0); // 从源点0开始
    return 0;
}

5.1.3 Java 代码实现

import java.util.Arrays;

public class DijkstraMatrix {
    private static final int V = 5;
    private static final int INF = Integer.MAX_VALUE;

    private int minDistance(int[] dist, boolean[] visited) {
        int min = INF;
        int minIndex = -1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && dist[v] <= min) {
                min = dist[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    public void dijkstra(int[][] graph, int src) {
        int[] dist = new int[V];
        boolean[] visited = new boolean[V];

        Arrays.fill(dist, INF);
        dist[src] = 0;

        for (int count = 0; count < V - 1; count++) {
            // 1. 选点
            int u = minDistance(dist, visited);
            if (u == -1) break;

            // 2. 标记
            visited[u] = true;

            // 3. 松弛
            for (int v = 0; v < V; v++) {
                if (!visited[v] && graph[u][v] != 0 && dist[u] != INF && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }

        printSolution(dist);
    }

    private void printSolution(int[] dist) {
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < V; i++) {
            System.out.println(i + "\t\t" + (dist[i] == INF ? "INF" : dist[i]));
        }
    }

    public static void main(String[] args) {
        int[][] graph = new int[][]{
            {0, 10, 3, 0, 0},
            {0, 0, 8, 1, 0},
            {0, 4, 0, 8, 2},
            {0, 0, 0, 0, 5},
            {0, 0, 0, 0, 0}
        };
        DijkstraMatrix t = new DijkstraMatrix();
        t.dijkstra(graph, 0);
    }
}

5.2 基于优先队列（堆）的优化 ( $\log V)$ )

$O(V^2)$ 的实现在“选点”这一步耗费了大量时间。如果图是稀疏的（边数 E 远小于 $V^2$ ），这种实现就非常浪费。

5.2.1 优化的关键：为什么用优先队列？

“选点”的本质是在未访问的顶点中找到dist值最小的那个。这正是**优先队列（Min-Heap）**的专长！

我们可以将 (距离, 顶点) 二元组存入优先队列。

选点：直接从优先队列顶部取元素，时间复杂度从 $O (V)$ 降为 $O(\log V)$ 。
松弛：当 dist[v] 被更新时，将新的、更小的 (dist[v], v) 放入优先队列。

5.2.2 复杂度分析

时间复杂度:
- 每个顶点入队和出队一次，共 V 次，每次操作 $O(\log V)$ ，总计 $\log V)$ 。
- 每条边最多引起一次松弛操作（更新 dist 值），每次松弛会向优先队列中插入一个新元素，共 E 次，每次操作 $O(\log V)$ ，总计 $\log V)$ 。
- 综合起来，总时间复杂度为 $\log V + E \log V)$ 。对于连通图， $\ge V-1$ ，所以可以简化为 $\log V)$ 。
空间复杂度: 使用邻接表存储图，空间为 $O (V + E)$ 。优先队列最多存储 V 个元素，dist 和 visited 数组需要 $O (V)$ 。总空间复杂度为 $O (V + E)$ 。

5.2.3 C++ 代码实现

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

#define INF INT_MAX

// 定义图的邻接表表示
typedef pair<int, int> iPair; // (权重, 顶点)

void dijkstra_pq(int V, const vector<vector<iPair>>& adj, int src) {
    // 优先队列，存储<距离, 顶点>，默认为大顶堆，需转为小顶堆
    priority_queue<iPair, vector<iPair>, greater<iPair>> pq;
    
    vector<int> dist(V, INF);
    
    // 插入源点
    pq.push({0, src});
    dist[src] = 0;
    
    while (!pq.empty()) {
        // 1. 选点：自动选择dist最小的顶点u
        int u = pq.top().second;
        pq.pop();
        
        // 优化：如果一个顶点被处理过，则跳过
        // 因为队列中可能有旧的、距离更大的(dist, u)对
        if (dist[u] < pq.top().first && !pq.empty()) {
            continue;
        }

        // 2. 标记（隐式）：从队列中取出即视为处理
        // 3. 松弛
        for (auto& edge : adj[u]) {
            int v = edge.second;
            int weight = edge.first;
            
            if (dist[u] != INF && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push({dist[v], v}); // 将更新后的(距离, 顶点)放入队列
            }
        }
    }
    
    // 打印结果
    cout << "Vertex\tDistance from Source" << endl;
    for (int i = 0; i < V; ++i) {
        cout << i << "\t\t" << (dist[i] == INF ? "INF" : to_string(dist[i])) << endl;
    }
}

int main() {
    int V = 5;
    // 使用邻接表
    vector<vector<iPair>> adj(V);
    
    // 添加边，格式: adj[u].push_back({weight, v})
    adj[0].push_back({10, 1});
    adj[0].push_back({3, 2});
    adj[1].push_back({1, 3});
    adj[1].push_back({8, 2});
    adj[2].push_back({4, 1});
    adj[2].push_back({8, 3});
    adj[2].push_back({2, 4});
    adj[3].push_back({5, 4});

    dijkstra_pq(V, adj, 0);
    
    return 0;
}

5.2.4 Java 代码实现

import java.util.*;

public class DijkstraPriorityQueue {
    private static final int INF = Integer.MAX_VALUE;

    static class Node implements Comparable<Node> {
        public int vertex;
        public int distance;

        public Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }

    public void dijkstra(int V, List<List<Node>> adj, int src) {
        PriorityQueue<Node> pq = new PriorityQueue<>(V);
        int[] dist = new int[V];
        Arrays.fill(dist, INF);

        dist[src] = 0;
        pq.add(new Node(src, 0));

        while (!pq.isEmpty()) {
            // 1. 选点
            Node node = pq.poll();
            int u = node.vertex;

            // 优化
            if (node.distance > dist[u]) {
                continue;
            }

            // 3. 松弛
            for (Node neighbor : adj.get(u)) {
                int v = neighbor.vertex;
                int weight = neighbor.distance;

                if (dist[u] != INF && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.add(new Node(v, dist[v]));
                }
            }
        }
        
        printSolution(dist);
    }
    
    private void printSolution(int[] dist) {
        System.out.println("Vertex\tDistance from Source");
        for (int i = 0; i < dist.length; i++) {
            System.out.println(i + "\t\t" + (dist[i] == INF ? "INF" : dist[i]));
        }
    }

    public static void main(String[] args) {
        int V = 5;
        List<List<Node>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }
        
        adj.get(0).add(new Node(1, 10));
        adj.get(0).add(new Node(2, 3));
        adj.get(1).add(new Node(3, 1));
        adj.get(1).add(new Node(2, 8));
        adj.get(2).add(new Node(1, 4));
        adj.get(2).add(new Node(3, 8));
        adj.get(2).add(new Node(4, 2));
        adj.get(3).add(new Node(4, 5));

        DijkstraPriorityQueue solver = new DijkstraPriorityQueue();
        solver.dijkstra(V, adj, 0);
    }
}

六、Dijkstra 算法的局限性

Dijkstra 算法功能强大，但它有一个致命的弱点。

6.1 致命弱点：无法处理负权边

Dijkstra 算法的贪心策略成立的基础是：一旦一个顶点被标记为 visited，其 dist 值就不会再被更新。这是因为所有边权都是非负的，任何绕行路径的长度都不可能比当前已找到的路径更短。

但是，如果图中存在负权边，这个前提就被打破了。

反例：

从 A 出发：

初始化: dist = {A:0, B:inf, C:inf}, visited = {}
第一次迭代: 选择 A。更新 dist = {A:0, B:3, C:5}。
第二次迭代: 选择 B (dist=3)。将 B 加入 visited。更新 B 的邻居 C：dist[B] + w(B,C) = 3 + (-4) = -1 < dist[C]。所以 dist[C] 更新为 -1。此时 dist = {A:0, B:3, C:-1}。
第三次迭代: 选择 C (dist=-1)。

最终结果 dist[C] = -1 是正确的。但是，如果图再复杂一点呢？

错误示例：

从 A 出发：

第一次迭代: 选择 A，更新 dist={B:1, D:10}。
第二次迭代: 选择 B (dist=1)，将其标记为 visited。此时算法认定 A->B 的最短路就是1。然后更新 C，dist[C]=3。
第三次迭代: 选择 C (dist=3)。
第四次迭代: 选择 D (dist=10)。更新 B: dist[D]+w(D,B) = 10-10=0 < dist[B]。但是，B 已经被标记为 visited，Dijkstra 算法不会再去更新它！

算法最终会给出 A->B 的最短路是 1，但实际上 A->D->B 的路径长度是 0。Dijkstra的贪心选择过早地确定了到 B 的路径，导致了错误。

结论：当图中存在负权边时，必须使用其他算法，如 Bellman-Ford 算法 或 SPFA 算法（将在后续文章中介绍）。

七、应用场景

Dijkstra 算法因其高效和直观，在没有负权边的场景下应用极为广泛：

网络路由协议：如 OSPF (开放最短路径优先) 协议，在路由器之间交换链路状态信息，并使用 Dijkstra 算法计算路由表。
地图导航：GPS 系统在计算两个地点间的最快或最短路线时，可以将交叉路口看作顶点，道路看作边，行驶时间或距离看作权重。
社交网络：计算两个人之间的“最短关系链”。
生物信息学：在基因调控网络中寻找最短的调控路径。

八、总结

本文系统地介绍了单源最短路径问题的经典解法——Dijkstra 算法。现在，让我们对核心知识点进行回顾：

核心思想：Dijkstra 是一种基于贪心策略的算法。它维护一个 dist 数组和一个 visited 集合，每次选择当前已知距离源点最近的未访问顶点，确定其最短路径，并用它来“松弛”其邻居的距离。
实现方式：
- 朴素实现（邻接矩阵）：通过线性扫描查找 dist 最小的顶点，时间复杂度为 $O(V^2)$ ，适用于稠密图。
- 优化实现（优先队列+邻接表）：利用优先队列（堆）快速获取 dist 最小的顶点，时间复杂度降至 $\log V)$ ，是稀疏图上的首选方案。
关键局限性：Dijkstra 算法的正确性依赖于边权的非负性。它无法正确处理带有负权边的图。
下篇预告：既然 Dijkstra 无法处理负权边，那么当现实问题中出现“返利”、“消耗减少”等负权场景时，我们该如何应对呢？下一篇文章，我们将学习能够完美解决带负权边问题的 Bellman-Ford 算法。

乐奇 Rokid 开放社区

更多推荐

使用Rokid AIUI做了一个童年推箱子游戏

乐奇 Rokid 开放社区

基于 AIUI 框架的眼镜端坐姿监测智能体：WorkerMonitor 设计与实现

基于AIUI框架，设计并实现眼镜端坐姿监测智能体WorkerMonitor。通过加速度传感器实时采集头部姿态数据，结合校准偏移量进行三态分类（正常/警示/异常），每秒采样一次，累计时长并低打扰提醒。每2小时调用LLM生成个性化健康建议，支持自动工作/休息切换与隐藏模式，兼顾隐私与体验。项目采用Ink单文件页面结构，实现极简交互与可持续反馈，为长期伏案者提供无感式颈椎健康管理方案。

乐奇 Rokid 开放社区

FPC与机器人的双向赋能，解锁智能装备进化新势能

如果说AI算法、算力芯片是智能眼镜的“智慧大脑”，光学模组是智能眼镜的“视觉窗口”，那么FPC就是贯穿整机、连接所有功能模块的“柔性神经脉络”。方寸之间的柔性突破，破解了智能眼镜“轻薄形态”与“全能功能”的核心矛盾，是穿戴智能设备实现形态革新、体验升级的底层核心。未来，随着AR沉浸式技术、AI大模型、穿戴硬件技术的持续进化，智能眼镜将朝着更轻薄、更智能、更多场景、更高稳定性的方向持续迭代，对高端精

乐奇 Rokid 开放社区

所有评论(0)

查看更多评论

大模型铲屎官

@Kiradzy

已为社区贡献5条内容

【数据结构与算法-Day 46】图解最短路径：Dijkstra算法从原理到实战（无负权边）

数据结构与算法系列文章目录

文章目录

摘要

一、引言：最短路径问题是什么？

1.1 生活中的最短路径

1.2 问题的形式化定义

二、Dijkstra 算法的核心思想：贪心的智慧

2.1 算法的直观理解

2.2 核心三要素

2.2.1 dist 数组：距离记录本

2.2.2 visited 集合：已确定最短路径的顶点

2.2.3 松弛 (Relaxation) 操作：更新最短路径

三、算法执行步骤详解

3.1 初始化

3.2 迭代过程（循环 V 次）

3.2.1 选点：选择 dist 值最小的未访问顶点 u

3.2.2 标记：将 u 加入 visited 集合

3.2.3 松弛：更新 u 的所有邻接点

3.3 流程图可视化

四、Dijkstra 算法的实例演练

4.1 示例图

4.2 分步图解

五、代码实现：从朴素到优化

5.1 基于邻接矩阵的实现 ( O ( V 2 ) O(V^2) O(V2))

5.1.1 复杂度分析

5.1.2 C++ 代码实现

5.1.3 Java 代码实现

5.2 基于优先队列（堆）的优化 ( O ( E log ⁡ V ) O(E \log V) O(ElogV))

5.2.1 优化的关键：为什么用优先队列？

5.2.2 复杂度分析

5.2.3 C++ 代码实现

5.2.4 Java 代码实现

六、Dijkstra 算法的局限性

6.1 致命弱点：无法处理负权边

七、应用场景

八、总结

所有评论(0)

温馨提示：您尚未绑定手机号

2.2.1 `dist` 数组：距离记录本

2.2.2 `visited` 集合：已确定最短路径的顶点

3.2.1 选点：选择 `dist` 值最小的未访问顶点 `u`

3.2.2 标记：将 `u` 加入 `visited` 集合

3.2.3 松弛：更新 `u` 的所有邻接点

5.1 基于邻接矩阵的实现 ( $O(V^2)$ )

5.2 基于优先队列（堆）的优化 ( $\log V)$ )