用Matlab实现迪杰斯特拉
时间: 2023-12-25 09:58:39 浏览: 33
好的,我可以为您提供一个简单的Matlab实现,以下是代码:
```matlab
function [distances, path] = dijkstra(graph, start_node, end_node)
% Dijkstra's algorithm to find the shortest path between two nodes in a graph
% Inputs:
% graph: adjacency matrix representing the graph
% start_node: starting node
% end_node: ending node
% Outputs:
% distances: array of distances from the starting node to each node
% path: array of the shortest path from the starting node to the ending node
n = size(graph, 1); % number of nodes in the graph
distances = Inf(1, n); % initialize all distances to infinity
distances(start_node) = 0; % distance from start node to itself is 0
visited = zeros(1, n); % mark all nodes as unvisited
path = zeros(1, n); % initialize path array
for i = 1:n-1 % repeat n-1 times
% find the unvisited node with the smallest tentative distance
min_distance = Inf;
for j = 1:n
if visited(j) == 0 && distances(j) < min_distance
min_distance = distances(j);
current_node = j;
end
end
visited(current_node) = 1; % mark the current node as visited
% update the distance and path arrays for neighboring nodes
for j = 1:n
if graph(current_node, j) ~= 0 && visited(j) == 0
tentative_distance = distances(current_node) + graph(current_node, j);
if tentative_distance < distances(j)
distances(j) = tentative_distance;
path(j) = current_node;
end
end
end
end
% construct the shortest path array
path_nodes = end_node;
while path(path_nodes) ~= start_node
path_nodes = [path(path_nodes), path(path_nodes)];
end
path_nodes = [start_node, path_nodes, end_node];
path = fliplr(path_nodes);
end
```
这个函数的输入是一个邻接矩阵,表示图的连接关系,以及起始节点和结束节点。它的输出是距离数组和路径数组,分别表示从起始节点到每个节点的距离和从起始节点到结束节点的最短路径。