已知无向图加权如何确定两点最短路径 matlab

Question

如题所述

Answer 1

已知无向图加权如何确定两点最短路径 matlab
function [L,Z]=dijkstra(W,S,T)
%用 Dijkstra 算法求最短路径
% 算法
% 1. 对每个点I指定一个离点S的距离初始值L(I). 在始点S的值为零, 即L(S)=0，其它点的值为Inf.
% 2. 所有的点标记为未走访的. 置始点S为当前点C.
% 3. 对于当前点C, 考虑它的所有未走访的相邻点J, 并更新J的距离值为
% L(J)=min(L(J), L(C)+W(C,J))
% 4. 把当前点C标记为走访过的点. 走访过的点C的距离L(C)就是点S到C的最短距离, 而且以后不再检查走访过得点了.
% 5. 如果所有的点都是走访过的点, 完成. 不然, 把未走访的点中具有最小距离值的点作为下一个当前点C, 转
N=length(W(:,1));%顶点数
W(find(W==0))=inf;
L=Inf*ones(1,N);
L(S)=0;%L赋初值，在S点为0，其它点为Inf
C=S; %当前点为始点S
Q=1:N;% 未走访的顶点集
Z=S*ones(1,N);
Z(S)=0;% Z赋初值,因始点 S 无父亲点,故把 S 点的Z值改为0
for K=1:N % 更新 L 和 Z 的循环