查看: 1598|回复: 0

Dijkstra算法求c1点到其余各点的最短路径

字体大小: 正常放大

1192 主题	4 听众	2946 积分

该用户从未签到

电梯直达

1^#

发表于 2024-10-23 15:59 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

该 MATLAB 代码实现了 Dijkstra 算法，用于求解单源最短路径问题。该算法用于计算从一个节点（通常是起始节点）到其他所有节点的最短路径。下面是对代码的逐行分析和对算法思想的解释：

### Dijkstra 算法的基本思想

Dijkstra 算法是一种贪心算法，核心思想是通过不断选择当前未访问节点中距离起点最近的节点，并更新相邻节点的最短路径估计值，最终找到所有节点的最短路径。

代码解析

[color=rgba(6, 8, 31, 0.88)]函数定义:

function [d, index1, index2] = dijkf(a)

复制代码

- `a` 为权值矩阵，表示图中节点之间的边的权重。
- `d` 为最短路径权重的数组。
- `index1` 表示节点访问顺序。
- `index2` 表示节点的索引顺序。

[color=rgba(6, 8, 31, 0.88)]初始化[color=rgba(6, 8, 31, 0.88)]:

M = max(max(a)); , H. @, {5 |& k. ?) T' @9 l
pb(1:length(a)) = 0; % 标记所有节点为未访问 ( Y- I1 A5 }9 J/ n2 d9 E; v# L, T2 h' j
pb(1) = 1; % 将起点标记为已访问
# {. j% x' a1 f$ ~+ k2 ]# Z8 b
index1 = 1; % 记录访问顺序 $ i$ l3 ^ [0 Y! S' x
index2 = ones(1, length(a)); % 初始化索引数组
, j# @3 s& K- Y$ s& A3 s
d(1:length(a)) = M; % 初始化距离数组为最大值
, S\" p+ ^ ?6 K\" g7 K7 \6 J
d(1) = 0; % 起点到自身的距离为0 ' V/ c5 T* {! }! N1 I1 Q
temp = 1; % 设定当前节点为起点

复制代码

- 通过提取权值矩阵的最大值来设置初始距离为一个很大的数（无穷大）。
- `pb` 数组用于标记哪些节点已被访问。
- `d` 数组用于存储从起点到其他节点的最短路径长度，初始时将所有值设为无穷大，起点到自身的距离设为0。

[color=rgba(6, 8, 31, 0.88)]更新最短路径[color=rgba(6, 8, 31, 0.88)]::

while sum(pb) < length(a) ' v4 O3 H; @5 H7 w4 {
tb = find(pb == 0); % 找到所有未访问的节点
0 ], o2 `- ^5 u0 h8 l3 h5 h
d(tb) = min(d(tb), d(temp) + a(temp, tb)); % 更新这些节点的距离 # o8 Q. z7 t5 M* S- U
tmpb = find(d(tb) == min(d(tb))); % 找到距离最小的未访问节点
- k8 ~' a3 o7 J) v$ N! }
temp = tb(tmpb(1)); % 选择距离最小的那个节点
k3 d( F, _# R, n
pb(temp) = 1; % 将其标记为已访问 $ M# c3 _4 v3 k9 O( q
index1 = [index1, temp]; % 记录访问顺序

复制代码

- 使用 `while` 循环遍历所有节点，直至所有节点都被访问。
- 找到当前未访问节点 `tb`，并更新这些节点的最短路径长度。
- 选择距离最小的未访问节点来作为下一个要访问的节点。
- 将该节点标记为已访问，并记录访问顺序。

[color=rgba(6, 8, 31, 0.88)]记录顺序和索引[color=rgba(6, 8, 31, 0.88)]:

index = index1(find(d(index1) == d(temp) - a(temp, index1))); 7 u% I+ R8 W5 K\" M; Z; k; x9 z
if length(index) >= 2
1 w& i& ?# x) f1 ^/ ?0 Q
index = index(1); 1 M. e8 F2 ]4 a/ ^\" w1 d, l! \( _6 o
end & e* W0 l$ y' e% g4 }\" z0 `
index2(temp) = index; % 将更新后的索引存入 index2

复制代码

- 通过计算当前节点与已访问节点的关系来更新节点索引 `index2`，确保最短路径的方向正确。

总结最后，该算法实现了 Dijkstra 最短路径算法的基本逻辑：

1. 初始化距离和访问标记。
2. 循环获取离起点最近的未访问节点，并更新其邻接节点的最短路径。
3. 重复这一过程，直到所有节点均被访问。

最终返回的 `d` 是从起点到其他节点的最短路径长度数组，`index1` 是访问顺序，`index2` 是节点的索引顺序。这个算法的时间复杂度为 $O(V^2)$，其中 $V$ 是图中节点的数量。但在使用优先队列等数据结构优化时，可以将复杂度降低到 $O((V + E) \log V)$，$E$ 是边的数量。