matlab的floyd算法代码
时间: 2023-11-13 18:54:00 浏览: 45
以下是Matlab实现的Floyd算法代码:
```matlab
function [D, P] = floyd(W)
% FLOYD - Floyd's all-pairs shortest path algorithm
% [D, P] = FLOYD(W) returns the all-pairs shortest path matrix D and the
% predecessor matrix P of the weighted graph W. Inf is used for missing
% edges. The (i,j)-th entry of D contains the shortest path distance from
% vertex i to vertex j. The (i,j)-th entry of P contains the predecessor
% vertex of j on a shortest path from i to j. If there are multiple
% shortest paths, the predecessor is arbitrarily chosen.
%
% Example:
% W = [0 1 3 Inf; Inf 0 Inf 2; Inf Inf 0 Inf; Inf Inf 1 0];
% [D, P] = floyd(W)
%
% Reference:
% R. W. Floyd, "Algorithm 97: Shortest path," Communications of the
% ACM, vol. 5, no. 6, p. 345, 1962.
%
% See also BELLMANFORD, JOHNSON.
n = size(W, 1);
D = W;
P = repmat(1:n, n, 1);
for k = 1:n
for i = 1:n
for j = 1:n
if D(i,k) + D(k,j) < D(i,j)
D(i,j) = D(i,k) + D(k,j);
P(i,j) = P(k,j);
end
end
end
end
end
```
其中,输入参数W是一个n×n的矩阵,表示带权有向图的邻接矩阵,其中W(i,j)表示从顶点i到顶点j的边的权值,如果不存在这样的边,则W(i,j)为Inf。输出参数D是一个n×n的矩阵,表示所有顶点对之间的最短路径长度,其中D(i,j)表示从顶点i到顶点j的最短路径长度。输出参数P是一个n×n的矩阵,表示所有顶点对之间的最短路径上的前驱顶点,其中P(i,j)表示从顶点i到顶点j的最短路径上,顶点j的前驱顶点。