【MATLAB】求到其余各点最短路径Dijkstra算法

在MATLAB中，你可以使用`dijkstra`函数来计算图中的最短路径，这通常适用于无权图或者权重非负的有向图。Dijkstra算法是一种贪心算法，用于寻找两点之间的最短路径。以下是基本步骤：

1. **创建图**：首先，你需要定义一个邻接矩阵或邻接列表表示你的图。可以使用`graph`函数来创建。

adjMatrix = [0 4 0 0; ... % 矩阵元素代表边和距离
             4 0 8 0;
             0 8 0 5;
             0 0 5 0]; % 注意，无连接则对应值设为0
G = graph(adjMatrix);

2. **调用Dijkstra函数**：然后使用`dijkstra(G, sourceNode)`，这里的`sourceNode`是你希望从哪一点开始搜索的节点索引。它会返回一个标量向量，其中包含了所有其他节点相对于`sourceNode`的最短距离。

[D, pred] = dijkstra(G, 1); % 从第一个节点（假设为1）开始找最短路径

`D`是一个一维数组，存储了每个节点的距离；`pred`是一个一维数组，记录了每个节点到达当前节点的前驱节点索引。

3. **获取路径**：如果需要找到完整的路径，可以利用`pred`数组反向追溯。例如，从目标节点到源节点的路径可以用`path = G.preds(pred(end:-1:2),1)`, 其中`preds`是`graph`对象的一个属性，包含邻接表形式的前驱信息。

相关问题

【MATLAB】起点到其余点最短路径Dijkstra算法

MATLAB中的Dijkstra算法是一种用于寻找图中两点之间最短路径的常用算法，其基本思想是从起点开始，逐步更新每个未访问节点的最短路径，直到找到所有节点的最短路径。以下是使用MATLAB实现Dijkstra算法的步骤：

1. **数据准备**：首先，你需要创建一个稀疏矩阵表示图，其中非零元素表示边的存在及其权重。

graph = sparse(source_nodes, target_nodes, edge_weights);

这里的`source_nodes`是起点列表，`target_nodes`是终点列表，`edge_weights`是对应的边的权重。

2. **初始化**：设置起点的最短距离为0，其他所有节点的距离设为无穷大，并创建一个标记数组标记哪些节点已经被处理过。

dist = Inf(size(graph, 1), 1); % 初始化距离
visited = false(size(graph, 1), 1); % 初始化已访问标志
dist(start_node) = 0; % 起点距离设为0

3. **迭代过程**：通过不断选择当前未访问且距离最小的节点，更新与其相邻节点的距离，直到所有节点都被处理过或者找不到更优路径为止。

while ~all(visited)
    [u, ~] = min(dist .* ~visited); % 找到未访问的最近节点
    visited(u) = true;
    
    for v = find(graph(:, u)) % 遍历u的所有邻接节点
        if dist(v) > dist(u) + graph(u, v) % 如果新路径更短
            dist(v) = dist(u) + graph(u, v);
        end
    end
end

4. **结果获取**：`dist(end)`就是目标节点的最短距离，而`[~, path] = min([dist; Inf], [], 2);`可以返回从起点到目标节点的最短路径索引序列。

MATLAB求最短路径Dijkstra算法路径可视化代码

在MATLAB中，Dijkstra算法用于寻找图中两点之间的最短路径。路径可视化通常会用到graph对象和plot函数。以下是使用Dijkstra算法并将其结果可视化的简单示例：

% 创建一个有权图
G = graph([1 4 6; 2 4 8; 3 5 9; 4 7], [5 1 2; 2 8 3; 6 9; 4 7]);

% 确定源点（起始节点）
source = 1;

% 使用dijkstra函数计算最短路径
[D, shortest_paths] = dijkstra(G, source);

% 将边权重赋值给颜色，这里假设路径长度对应于颜色深浅
edge_weights = full(G.Edges.Weight);
edge_colors = colormap('hot') / edge_weights';

% 绘制原图和最短路径
figure;
h = plot(G, 'NodeColor', 'k', 'EdgeColor', edge_colors);
hold on;
% 使用shortest_paths数组的索引来连接起点和终点
path_edges = sub2ind(size(D), shortest_paths(:,2), shortest_paths(:,1));
plot(h, path_edges, '-r', 'LineWidth', 2); % 红色表示最短路径

% 添加标题和轴标签
title(sprintf('Shortest Path from Node %d', source));
xlabel('Node Index');
ylabel('Node Index');

% 显示所有路径
disp('Press any key to show all paths:');
pause;

% 显示所有节点之间的路径
for i = 1:numel(shortest_paths)
    if i == 1 || i == numel(shortest_paths)
        continue; % 跳过起点和终点
    end
    plot(h, [shortest_paths(i,1) shortest_paths(i+1,1)], '-b', 'LineWidth', 1); % 蓝色线段代表单步路径
end

% 清理显示
hold off;