贪心算法求解最短路径问题matlab

function [distances, path] = greedyShortestPaths(adjMatrix, start) % 输入: % adjMatrix - 图的邻接矩阵，adjMatrix(i,j)是从节点i到节点j的权重 % start - 起始节点的索引 % 输出: % distances - 从起始节点到所有其他节点的最短距离 % path - 最短路径（从起始节点到每个节点的路径上的前一个节点） numNodes = size(adjMatrix, 1); distances = inf(1, numNodes); % 初始化距离数组为无穷大 distances(start) = 0; % 起始节点到自身的距离为0 path = zeros(1, numNodes); % 初始化路径数组 path(start) = -1; % 起始节点没有前一个节点 visited = false(1, numNodes); % 标记节点是否已访问 % 贪心算法主循环 while sum(visited) < numNodes % 找出当前未访问节点中距离最小的节点 [~, nextNode] = min(distances(logical(~visited))); visited(nextNode) = true; % 标记为已访问 % 更新相邻未访问节点的距离和路径 for i = 1:numNodes if ~visited(i) && adjMatrix(nextNode, i) > 0 && ... distances(nextNode) + adjMatrix(nextNode, i) < distances(i) distances(i) = distances(nextNode) + adjMatrix(nextNode, i); path(i) = nextNode; end end end end % 示例使用 adjMatrix = [0, 1, 5, 2; 1, 0, 3, 6; 5, 3, 0, 4; 2, 6, 4, 0]; start = 1; [distances, path] = greedyShortestPaths(adjMatrix, start); disp('Distances from start node:'); disp(distances); disp('Path (predecessor node for each node):'); disp(path);