matlab贪心算法编写最短路径问题

最短路径问题可以使用贪心算法来解决。下面是一个简单的贪心算法实现最短路径问题的MATLAB代码：

function [path, cost] = dijkstra(graph, start, target)
% Dijkstra算法实现最短路径问题
% graph: 图的邻接矩阵
% start: 起点
% target: 终点
% path: 路径
% cost: 路径长度

n = size(graph, 1); % 图中节点数量
visited = zeros(n, 1); % 标记节点是否已被访问
distance = Inf(n, 1); % 记录起点到每个节点的距离
predecessor = zeros(n, 1); % 记录每个节点的前驱节点

distance(start) = 0; % 起点到自己的距离为0

while sum(visited) < n
    % 选择未访问的节点中距离起点最近的节点
    [~, u] = min(distance .* (1 - visited));
    visited(u) = 1;
    
    % 更新起点到其他节点的距离
    for v = 1:n
        if graph(u, v) > 0 && distance(u) + graph(u, v) < distance(v)
            distance(v) = distance(u) + graph(u, v);
            predecessor(v) = u;
        end
    end
end

% 从终点向起点回溯，得到路径和路径长度
path = target;
u = target;
while u ~= start
    u = predecessor(u);
    path = [u, path];
end
cost = distance(target);
end

该算法通过邻接矩阵表示图，使用visited数组记录节点是否已被访问过，使用distance数组记录起点到每个节点的距离，使用predecessor数组记录每个节点的前驱节点。算法的核心是不断选择未访问的节点中距离起点最近的节点，并更新起点到其他节点的距离，直到所有节点都被访问过。最终从终点向起点回溯，得到路径和路径长度。