MATLAB实现Dijkstra算法：从邻接矩阵到内置函数的路径规划实战

1. 项目概述：从理论到实践的路径规划

在工程计算、科研仿真乃至算法教学领域，我们常常面临一个核心问题：如何在由节点和连接构成的复杂网络中，找到两点之间成本最低的路径？无论是交通网络中的最短行车路线、通信网络中的最优数据传输链路，还是社交网络中的影响力传播分析，其底层逻辑都指向了图论中的最短路径问题。而Dijkstra算法，正是解决非负权重图单源最短路径问题的经典与基石。今天，我们不谈复杂的数学推导，而是聚焦于一个更实际的问题：如何将这一精妙的算法思想，在MATLAB这一强大的数值计算与原型开发环境中，从理论公式转化为一行行清晰、高效、可复用的代码？

我接触过不少初学者，他们理解了算法的步骤，却在用MATLAB实现时感到无从下手，或者写出的代码效率低下、可读性差，只能处理教科书上的简单例子，一旦面对稍具规模的矩阵就束手无策。这背后的原因，往往在于没有建立起从“算法伪代码”到“MATLAB矩阵化思维”的桥梁。本文将分享我多次实现和优化Dijkstra算法的经验，不仅会给出可直接运行的代码，更会深入剖析每一步的MATLAB实现技巧、不同数据结构的性能差异，以及在实际应用中可能遇到的“坑”和应对策略。无论你是正在完成课程作业的学生，还是需要在科研项目中快速验证路径规划方案的研究者，这篇文章都将为你提供一个扎实的、工业级的实现参考。

2. 算法核心思想与MATLAB建模策略

在动手写代码之前，我们必须吃透Dijkstra算法的核心思想，并思考如何用MATLAB的数据结构来优雅地表达它。算法本质是一种贪心策略：从源点出发，逐步扩展到距离源点最近的未访问节点，并以此为基础，更新其邻居节点到源点的最短距离估计。这个“距离最近”的选取过程，是算法效率的关键。

2.1 算法流程的再梳理与关键变量

让我们抛开伪代码，用更工程化的语言描述一下流程：

1. 初始化：设定一个集合S，包含所有已找到最短路径的节点；一个数组dist，记录从源点到每个节点的当前最短距离估计；一个数组prev，记录到达每个节点的前驱节点（用于回溯路径）。初始时，S为空，dist中源点距离为0，其余为无穷大（Inf），prev全部为空。
2. 循环选取：在未加入S的节点集合中，选出dist值最小的节点u。此时可以证明，dist[u]就是源点到u的最终最短距离。将u加入S。
3. 松弛操作：对于节点u的每一个邻居节点v，检查如果经由u到达v是否更短，即判断dist[u] + weight(u, v) < dist[v]是否成立。如果成立，则更新dist[v] = dist[u] + weight(u, v)，并记录prev[v] = u。
4. 重复：重复步骤2和3，直到所有节点都加入S，或者目标节点已加入S（针对单源单目标情况）。

在MATLAB中，我们需要为这些抽象变量找到具体的载体：

• 图（Graph）：通常用邻接矩阵表示。adjMatrix(i, j)的值表示从节点i到节点j的边的权重。如果i和j不直接相连，则权重为Inf。对角线元素通常为0。对于无向图，矩阵是对称的。邻接矩阵非常直观，适合稠密图或节点数不是特别大的情况。
• 距离数组（dist）：一个一维向量dist(1:n)，n为节点总数。
• 前驱数组（prev）：一个一维向量prev(1:n)，用于存储路径。初始化为0或NaN。
• 已访问集合（S）：在MATLAB中，我们通常用一个布尔逻辑向量visited(1:n)来表示，visited(i)=true表示节点i已加入S。

注意：很多教学实现会用数组存储未访问节点集合并线性查找最小值，这在节点数多时效率极低（O(n²)）。在MATLAB中，我们可以利用矩阵运算和逻辑索引来优化，但更高效的做法是模拟优先队列的思想。

2.2 数据结构选型：邻接矩阵 vs. 邻接表

这是实现前必须做出的关键决策，直接影响代码的效率和内存占用。

邻接矩阵：

• 优点：实现简单，访问任意两节点间权重是O(1)操作。MATLAB对矩阵运算有深度优化，某些操作向量化后很快。
• 缺点：内存占用为O(n²)，对于稀疏图（边数远小于n²）极其浪费。在查找节点邻居时需要遍历整行，即使大多数是Inf。
• 适用场景：节点数量较少（例如几百个以内），或图非常稠密的教学、演示及小型仿真。

邻接表：

• 优点：内存占用为O(n+e)，与边数e成正比，非常适合稀疏图。可以快速获取一个节点的所有邻居。
• 缺点：MATLAB原生没有专门的图结构（虽然R2015b后引入了graph和digraph对象），需要自己用元胞数组或结构体数组实现，代码稍复杂。查找特定边(i,j)的权重需要遍历列表，效率为O(degree(i))。
• 适用场景：节点数量大、图稀疏的实际问题，如道路网络、社交网络。

对于本文，为了清晰展示算法与MATLAB基础语法（如矩阵索引、Inf、find函数）的结合，我们将首先采用邻接矩阵实现一个基础版本。在后续的优化章节，我们会探讨基于邻接表以及利用MATLAB内置图对象的更高效实现。理解基础矩阵版本，是迈向高级优化的必经之路。

3. 基础实现：邻接矩阵与循环版本

我们先实现一个最直观、最贴近算法伪代码的版本。这个版本使用完整的嵌套循环，易于理解，但效率不是最优。我们将通过它来巩固对算法步骤和MATLAB基本操作的理解。

3.1 函数接口设计与初始化

一个好的函数接口能让代码更易用。我们的Dijkstra函数至少需要输入邻接矩阵和源节点，输出最短距离和前驱节点。

function [dist, prev] = dijkstra_basic(adjMatrix, src) % DIJKSTRA_BASIC 使用邻接矩阵实现Dijkstra最短路径算法（基础循环版） % 输入： % adjMatrix - n x n 的邻接矩阵，adjMatrix(i,j)为边(i->j)的权值，无边则为Inf % src - 源节点编号（标量） % 输出： % dist - 1 x n 向量，dist(i)表示从源节点到节点i的最短距离 % prev - 1 x n 向量，prev(i)表示在最短路径上，节点i的前驱节点。用于路径回溯。 n = size(adjMatrix, 1); % 节点总数 dist = inf(1, n); % 初始化距离为无穷大 prev = zeros(1, n); % 初始化前驱为0 visited = false(1, n); % 标记节点是否已访问（即已加入S集合） dist(src) = 0; % 源节点到自身的距离为0

这里有几个细节：

1. size(adjMatrix, 1)获取行数，即节点数。我们假设输入的邻接矩阵是方阵。
2. inf(1, n)生成一个1行n列的全Inf向量。Inf在MATLAB中表示无穷大，是距离初始化的理想选择。
3. false(1, n)生成一个逻辑假向量，比用zeros(1,n)然后在比较时转换更高效、更清晰。
4. 前驱prev初始化为0，这是一个约定，因为MATLAB索引从1开始，0可以作为一个无效标识。后续回溯路径时，遇到0即停止。

3.2 主循环与“最近节点”选取

这是算法的核心循环。我们需要循环n次，每次从未访问节点中找出dist最小的那个。

for i = 1:n-1 % 循环n-1次即可，因为最后一次只剩一个节点无需比较 % 步骤1：在未访问节点中，找到当前距离最小的节点u minDist = inf; u = -1; % 初始化为无效节点 for v = 1:n if ~visited(v) && dist(v) < minDist minDist = dist(v); u = v; end end % 如果所有未访问节点距离都是Inf，说明剩余节点不可达，提前结束 if u == -1 break; end visited(u) = true; % 将节点u标记为已访问

这个双重循环是效率的瓶颈。外层循环n次，内层循环每次都要遍历n个节点来寻找最小值，因此总时间复杂度是O(n²)。对于小规模图（n<1000）尚可接受，但对于大规模图，这将非常缓慢。

3.3 松弛操作与邻居更新

找到当前最近节点u后，我们需要检查它的所有邻居v，看能否通过u缩短到v的距离。

% 步骤2：松弛操作，更新u的所有邻居的距离 for v = 1:n % 确保v是u的邻居（即边权不是Inf）且v未被访问 if ~visited(v) && adjMatrix(u, v) ~= inf alt = dist(u) + adjMatrix(u, v); if alt < dist(v) dist(v) = alt; prev(v) = u; end end end end end

这里的关键点是：

1. adjMatrix(u, v) ~= inf用于判断u和v是否直接相连。在邻接矩阵中，不存在的边用Inf表示。
2. alt是经由u到达v的候选距离。
3. 如果候选距离更短，就更新dist(v)和prev(v)。prev(v) = u意味着在最短路径上，到达v之前要先经过u。

3.4 路径回溯函数

算法输出了dist和prev数组，但用户通常想要的是具体的节点序列。我们需要一个辅助函数来根据prev数组回溯出从源点到任意目标点的路径。

function path = reconstructPath(prev, target) % RECONSTRUCTPATH 根据前驱数组prev回溯最短路径 % 输入： % prev - dijkstra函数输出的前驱向量 % target - 目标节点编号 % 输出： % path - 从源点到目标点的节点编号序列（行向量），如果不可达则为空数组 path = []; if prev(target) == 0 && target ~= src % 假设src是源点，这里需要额外传入，简易处理 % 目标节点不可达（前驱为0且不是源点自身） return; end % 从目标点向前回溯 u = target; while u ~= 0 % 约定源点的前驱为0 path = [u, path]; % 将当前节点插入路径头部 u = prev(u); end end

实操心得：在回溯路径时，将节点插入数组头部（[u, path]）会导致每次操作都涉及数组重排，当路径很长时效率不高。一个更高效的做法是先从目标点回溯到源点，将节点顺序存入一个栈（或反向数组），然后再反转。或者，可以预先分配一个足够大的数组，从后往前填充。对于教学和一般使用，当前方式足够清晰。

4. 优化实现：向量化与优先队列思想

基础循环版虽然直观，但其O(n²)的复杂度限制了应用范围。MATLAB的优势在于矩阵和向量运算。我们可以利用逻辑索引进行一定程度的向量化，并引入“优先队列”的思想来大幅优化“寻找未访问节点中dist最小者”这一步骤。

4.1 使用逻辑索引进行向量化更新

在松弛步骤中，我们不再显式循环遍历所有节点v，而是通过一次逻辑索引操作，找到所有u的未访问邻居，并向量化地更新它们的距离。

function [dist, prev] = dijkstra_vectorized(adjMatrix, src) n = size(adjMatrix, 1); dist = inf(1, n); prev = zeros(1, n); visited = false(1, n); dist(src) = 0; for i = 1:n-1 % 找到未访问节点中dist最小的节点u % 利用 ~visited 作为掩码，从dist中筛选出未访问节点的距离 tempDist = dist; tempDist(visited) = inf; % 将已访问节点的距离临时设为Inf，避免被选到 [minDist, u] = min(tempDist); if isinf(minDist) break; % 所有未访问节点都不可达 end visited(u) = true; % 向量化松弛操作 % 1. 找到u的所有未访问邻居 neighbors = ~visited & ~isinf(adjMatrix(u, :)); % 逻辑索引：未访问且边权有限 % 2. 计算经由u到这些邻居的候选距离 candidateDist = dist(u) + adjMatrix(u, neighbors); % 3. 比较并更新 updateMask = candidateDist < dist(neighbors); if any(updateMask) % 找出需要更新的邻居在原列表中的位置（有点绕） neighborIndices = find(neighbors); % 获取邻居节点的实际索引 indicesToUpdate = neighborIndices(updateMask); dist(indicesToUpdate) = candidateDist(updateMask); prev(indicesToUpdate) = u; end end end

优化解析：

1. 选取最小节点：tempDist(visited) = inf;这一行是关键。它创建了一个临时副本，并将已访问节点的距离设为Inf，这样min函数就会自动忽略它们。这避免了内层的for循环，利用MATLAB内置的、用C语言优化的min函数，速度更快。
2. 向量化松弛：
   • neighbors = ~visited & ~isinf(adjMatrix(u, :));生成一个逻辑向量，直接标出所有满足“未访问”且“与u相连”的节点。
   • candidateDist = dist(u) + adjMatrix(u, neighbors);一次性计算出所有候选距离。注意adjMatrix(u, neighbors)利用了逻辑索引，只取出u到这些邻居的权重。
   • updateMask = candidateDist < dist(neighbors);生成另一个逻辑向量，标记出哪些邻居需要更新。
   • 最后，通过find(neighbors)将逻辑索引转换为线性索引，只更新那些需要更新的节点。

这个版本比基础循环版快很多，尤其是当图的平均度数较高时。但它仍然需要每次循环都执行min(tempDist)，这本质上是一个线性扫描，复杂度仍是O(n²)。要突破这个瓶颈，我们需要引入优先队列。

4.2 模拟优先队列优化

在标准的算法教材中，使用优先队列（如二叉堆）可以将算法复杂度降至O((n+e) log n)。MATLAB没有内置的堆数据结构，但我们可以用一些技巧来模拟。

一种常见且有效的方法是维护两个并行列表：一个存储未访问节点的索引，另一个存储它们对应的当前距离。每次迭代，我们从这个列表中找出距离最小的节点。在更新邻居距离后，我们同步更新这个列表中的距离值。虽然查找最小值仍然是O(n)，但我们可以通过保持列表有序，或者使用min函数对较短的列表进行操作来获得一定提升。然而，最彻底的模拟是实现一个最小堆。

这里给出一个使用min函数但通过动态维护“未访问节点列表”来减少每次扫描数据量的简化版：

function [dist, prev] = dijkstra_optimized(adjMatrix, src) n = size(adjMatrix, 1); dist = inf(1, n); prev = zeros(1, n); visited = false(1, n); dist(src) = 0; % 初始化未访问节点列表为所有节点 unvisited = 1:n; while ~isempty(unvisited) % 在当前未访问节点列表中，找到dist最小的节点 [minDist, idxInList] = min(dist(unvisited)); u = unvisited(idxInList); if isinf(minDist) break; % 剩余节点均不可达 end visited(u) = true; % 从unvisited列表中移除u（效率关键点） unvisited(idxInList) = []; % 找出u的未访问邻居（在unvisited列表中的邻居） % 获取u的所有邻居索引（边权有限） allNeighbors = find(~isinf(adjMatrix(u, :)) & (adjMatrix(u, :) > 0)); % 通常排除自环和Inf % 求交集：allNeighbors 和 unvisited neighbors = allNeighbors(ismember(allNeighbors, unvisited)); for v = neighbors alt = dist(u) + adjMatrix(u, v); if alt < dist(v) dist(v) = alt; prev(v) = u; end end end end

注意事项：这个版本中，unvisited(idxInList) = []这行代码在MATLAB中效率较低，因为它需要移动数组元素。当节点数很大时，这会成为新的瓶颈。真正的优先队列实现需要自定义一个最小堆类，来支持O(log n)的提取最小值和更新键值操作。由于代码较长，这里不展开，但其思路是维护一个堆，堆顶始终是dist最小的未访问节点。每次松弛更新后，如果某个邻居的dist变小了，就需要将该节点在堆中的位置上浮（decrease-key操作）。

核心建议：对于大多数在MATLAB中处理中等规模图（节点数在几千到一两万）的场景，经过逻辑索引优化的dijkstra_vectorized版本通常是一个在实现复杂度和运行效率之间取得良好平衡的选择。除非你处理的是超大规模稀疏图（如全国路网），否则引入复杂的堆结构带来的性能提升可能不如直接使用MATLAB内置的图算法工具箱。

5. 使用MATLAB内置图对象与最短路径函数

从MATLAB R2015b开始，官方引入了graph和digraph对象，并提供了丰富的图算法函数，其中就包括shortestpath和distances函数，它们默认使用的就是Dijkstra算法（对于非负权重）。这是最推荐在生产代码或科研中使用的方案，因为它经过了高度优化，稳定且功能强大。

5.1 创建图对象并计算最短路径

假设我们有一个边的列表，包含起点、终点和权重。

% 示例：创建一个小型有向图 s = [1 1 2 3 3 4]; % 起点列表 t = [2 3 4 4 5 5]; % 终点列表 w = [10 5 2 9 3 4]; % 权重列表 G = digraph(s, t, w); % 创建有向加权图 % 如果是无向图，使用 graph(s, t, w) % 计算从节点1到节点5的最短路径和距离 [path, d] = shortestpath(G, 1, 5); disp(['最短路径：', num2str(path)]); disp(['最短距离：', num2str(d)]); % 计算从节点1到所有其他节点的最短距离 dist_all = distances(G, 1); disp('从节点1到各节点的距离：'); disp(dist_all);

优势分析：

1. 简洁高效：一两行代码解决问题，无需自己实现算法。
2. 功能全面：shortestpath函数自动处理路径回溯，distances函数计算单源或多源最短距离。
3. 性能优越：底层由C/C++实现，并针对稀疏矩阵进行了优化，速度远超一般的自写M文件。
4. 可视化集成：可以直接用plot(G)绘图，用highlight高亮最短路径，非常适合分析和演示。

5.2 处理邻接矩阵输入

如果你的数据已经是邻接矩阵形式，可以轻松地转换为图对象。

% 假设 adjMatrix 是你的 n x n 邻接矩阵 n = size(adjMatrix, 1); [s, t, w] = find(adjMatrix); % 找出所有非零（非Inf）元素的索引和值 % 注意：find会找到所有非零元素，包括对角线。如果对角线是0，需要排除。 nonDiagonal = (s ~= t); % 排除自环 s = s(nonDiagonal); t = t(nonDiagonal); w = w(nonDiagonal); % 将Inf权重转换为边？通常Inf表示无边，所以不应该加入图。 % 更安全的做法是，在创建adjMatrix时，不存在的边用0表示，然后： % [s, t, w] = find(adjMatrix); % G = digraph(s, t, w); % 或者使用稀疏矩阵直接构建：G = digraph(adjMatrix); 但要求adjMatrix是稀疏矩阵且权重在非零元素中。 % 推荐做法：如果原始数据是Inf表示无边，先将其替换为0 adjMatrixForGraph = adjMatrix; adjMatrixForGraph(isinf(adjMatrix)) = 0; G = digraph(adjMatrixForGraph, 'omitselfloops'); % 'omitselfloops'忽略自环

实操心得：当需要频繁对同一个图进行多次最短路径查询时，构建一次graph对象并重复调用shortestpath是最高效的方式。内置函数还支持指定算法（如'positive'对应Dijkstra，'unweighted'对应BFS等），非常灵活。

6. 实战应用与性能对比测试

理论再好，也需要实践检验。我们来设计一个简单的实验，对比我们实现的几个版本与MATLAB内置函数的性能，并展示一个实际应用场景。

6.1 性能对比实验

我们生成不同规模的随机图进行测试。

% 性能测试脚本 nodeSizes = [50, 100, 200, 500]; % 测试不同节点规模 results = cell(length(nodeSizes), 5); % 存储结果：节点数，基础版时间，向量化版时间，优化版时间，内置函数时间 for idx = 1:length(nodeSizes) n = nodeSizes(idx); fprintf('测试节点数 n = %d...\n', n); % 生成一个随机稀疏邻接矩阵（密度约10%） density = 0.1; adj = sprand(n, n, density); % 生成稀疏随机矩阵（0-1之间） adj = adj + speye(n); % 确保对角线为1（自环，距离为0） adj(adj > 0) = adj(adj > 0) * 10; % 给非零元素一个权重（1-10） % 将未连接的部分设为Inf（对于全矩阵操作，转为满矩阵） adjMatrix = full(adj); adjMatrix(adjMatrix == 0) = inf; adjMatrix(1:n+1:end) = 0; % 对角线置0 src = 1; % 计时：基础循环版 tic; [~, ~] = dijkstra_basic(adjMatrix, src); time_basic = toc; % 计时：向量化版 tic; [~, ~] = dijkstra_vectorized(adjMatrix, src); time_vec = toc; % 计时：优化列表版 tic; [~, ~] = dijkstra_optimized(adjMatrix, src); time_opt = toc; % 计时：内置函数（需转换为图对象） tic; adjForGraph = adjMatrix; adjForGraph(isinf(adjForGraph)) = 0; G = digraph(adjForGraph, 'omitselfloops'); dist_builtin = distances(G, src); time_builtin = toc; results{idx, 1} = n; results{idx, 2} = time_basic; results{idx, 3} = time_vec; results{idx, 4} = time_opt; results{idx, 5} = time_builtin; end % 展示结果 fprintf('\n性能对比结果（单位：秒）:\n'); fprintf('节点数\t基础循环\t向量化\t\t优化列表\t内置函数\n'); fprintf('------------------------------------------------------------\n'); for idx = 1:size(results, 1) fprintf('%d\t%.4f\t\t%.4f\t\t%.4f\t\t%.4f\n', ... results{idx,1}, results{idx,2}, results{idx,3}, results{idx,4}, results{idx,5}); end

预期结果分析：通常，基础循环版会最慢，向量化版有明显提升，优化列表版在小规模时可能不如向量化版（因为维护列表有开销），但在大规模稀疏图上优势会显现。而内置函数几乎总是最快的，并且优势随着规模增大而急剧扩大。这个实验能直观地告诉你，在什么场景下该选择哪种实现。

6.2 应用案例：校园导航路径规划

假设我们要为一个校园的若干地点规划最短路径。我们手动定义一个邻接矩阵，表示地点间的步行时间（分钟）。

% 定义地点：1-图书馆，2-教学楼A，3-教学楼B，4-食堂，5-体育馆，6-宿舍 n = 6; adjMatrix = inf(n); % 初始化为无穷大 adjMatrix(1,2)=5; adjMatrix(1,3)=8; adjMatrix(2,1)=5; adjMatrix(2,3)=2; adjMatrix(2,4)=10; adjMatrix(3,1)=8; adjMatrix(3,2)=2; adjMatrix(3,5)=4; adjMatrix(4,2)=10; adjMatrix(4,5)=3; adjMatrix(4,6)=12; adjMatrix(5,3)=4; adjMatrix(5,4)=3; adjMatrix(5,6)=6; adjMatrix(6,4)=12; adjMatrix(6,5)=6; % 无向图，所以矩阵本应是对称的，上面已经手动对称赋值了。 adjMatrix(1:n+1:end) = 0; % 对角线置0 src = 6; % 从宿舍出发 target = 1; % 去图书馆 % 使用我们的向量化实现 [dist, prev] = dijkstra_vectorized(adjMatrix, src); path = reconstructPath(prev, target); % 需要稍作修改，将src作为参数传入 fprintf('从宿舍到图书馆的最短步行时间：%.1f 分钟\n', dist(target)); fprintf('路径：'); for i = 1:length(path) fprintf('%d ', path(i)); if i < length(path) fprintf('-> '); end end fprintf('\n'); % 使用内置函数验证 G = graph(adjMatrix, 'upper', 'omitselfloops'); % 'upper'因为我们的矩阵是对称的 [path_builtin, dist_builtin] = shortestpath(G, src, target); fprintf('\n内置函数验证结果：\n'); fprintf('距离：%.1f 分钟\n', dist_builtin); fprintf('路径：%s\n', num2str(path_builtin));

这个简单的案例展示了如何将实际问题抽象为图，并用Dijkstra算法求解。你可以很容易地将其扩展，例如从文件读取更大的地图数据，或者将权重替换为实际的距离、时间、成本等。

7. 常见问题与调试技巧

在实现和使用Dijkstra算法时，你可能会遇到一些典型问题。这里总结一份排查清单。

调试技巧：

1. 从小图开始：用一个只有4-5个节点的、你手工能算出结果的图来测试你的算法。打印出每次循环后的dist、visited和prev数组，与你的手动计算过程对比。
2. 使用MATLAB调试器：在关键行设置断点，观察变量状态。特别是检查选取最小节点u是否正确，以及松弛操作是否按预期更新了邻居。
3. 可视化：对于小型图，用plot(graph(adjMatrix))把图画出来，直观地检查边和权重。用highlight函数标出算法计算出的最短路径，看是否合理。
4. 性能剖析：使用MATLAB的profile工具（在命令行输入profile on，运行你的函数，再输入profile viewer）查看代码的“热点”，即最耗时的部分，针对性地优化。

实现Dijkstra算法是理解图论算法和MATLAB矩阵编程的绝佳练习。从最基础的双重循环开始，逐步优化到向量化操作，最终过渡到使用成熟的内置工具箱，这个过程中对算法细节、数据结构选择和MATLAB语言特性的思考，其价值远超过仅仅调通一个函数。当你需要处理一个全新的、没有现成工具的图算法问题时，这段经历积累的经验将至关重要。