迪杰斯特拉算法的源代码 matlba
时间: 2023-10-09 13:07:51 浏览: 45
以下是 MATLAB 中实现 Dijkstra 算法的示例代码:
```matlab
function [distances, previous] = dijkstra(adjacency_matrix, start_node)
% DIJKSTRA finds the shortest path distance from a start node to all other nodes in a graph.
% [distances, previous] = DIJKSTRA(adjacency_matrix, start_node) returns an array of the shortest
% path distances from the start node to all other nodes in the graph, and an array of the previous
% node that leads to the corresponding node on the shortest path.
%
% adjacency_matrix is a square matrix that represents the weighted adjacency matrix of the graph.
% start_node is the node index of the start node.
%
% Example:
% adjacency_matrix = [0 2 4 Inf Inf; 2 0 1 4 2; 4 1 0 3 Inf; Inf 4 3 0 1; Inf 2 Inf 1 0];
% start_node = 1;
% [distances, previous] = dijkstra(adjacency_matrix, start_node);
%
% Author: Minjie Fan, minjief@gmail.com
num_of_nodes = size(adjacency_matrix, 1);
visited = false(num_of_nodes, 1);
distances = Inf(num_of_nodes, 1);
previous = nan(num_of_nodes, 1);
distances(start_node) = 0;
for i = 1:num_of_nodes
current_node = find(!visited & (distances == min(distances)));
if isempty(current_node)
break;
end
current_node = current_node(1);
visited(current_node) = true;
neighbors = find(adjacency_matrix(current_node, :) ~= Inf);
for neighbor = neighbors
tentative_distance = distances(current_node) + adjacency_matrix(current_node, neighbor);
if tentative_distance < distances(neighbor)
distances(neighbor) = tentative_distance;
previous(neighbor) = current_node;
end
end
end
end
```
使用示例:
```matlab
adjacency_matrix = [0 2 4 Inf Inf; 2 0 1 4 2; 4 1 0 3 Inf; Inf 4 3 0 1; Inf 2 Inf 1 0];
start_node = 1;
[distances, previous] = dijkstra(adjacency_matrix, start_node);
```
其中,`adjacency_matrix` 表示图的权重邻接矩阵,`start_node` 表示起始节点索引。返回结果包括每个节点到起始节点的最短路径长度(`distances`)和上一步节点的索引(`previous`)。