#################本文为学习《图论算法及其MATLAB实现》的学习笔记#################
算法用途
从一固定点到其他所有点的最短路的求法
算法思想
利用求任意两点间最短路的程序,即可求出从固定点到其他所有点的最短路,从而得到所有的最短路和最短距离。
若想查看每条通路所包含的顶点,则可通过查看返回值Pm来获得,如在命令行输入Pm{3},即可看到顶点k与3之间最短通路所包含的顶点,D(3)则为与该通路相应的长度
程序参数说明
W: 图的权值矩阵
k: 固定点
Pm{i}: 从固定点到顶点 i 的路径
D{i}: 从固定点到顶点 i 的距离
算法的matlab程序详解
其中调用的 n2shortf() 函数详情
%从固定点到其他所有点的最短通路
function [ Pm, D ] = ktonshf( W,k )
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%% 输入: W: 图的权值矩阵
%%%%%%%%% k: 固定点
%%%%%%%%% 输出: Pm{i}: 从固定点到顶点 i 的路径
%%%%%%%%% D{i}: 从固定点到顶点 i 的距离
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
n = size(W,1); % 计算总顶点数
D = zeros(1,n); % D 为最短距离数组
for i = 1:n
[p ,d] = n2shorf(W,k,i); % 调用 n2shorf,计算顶点 k 与 i 之间的最短路及其长度
Pm{i} = p;
D(i) = d;
end
%%%%%%%%%% 使用说明 %%%%%%%%%%
% 要查看每条通路所包含的顶点,应在获得返回值 Pm 之后
% E.g. 在命令行输入 Pm{3},即可看到顶点 k 与 3 之间最短路所包含的顶点
% D(3) 为该通路的长度
标签:通路,固定点,短路,%%%%%%%%%,matlab,顶点,Pm
From: https://blog.csdn.net/weixin_72217561/article/details/141750752