Dijkstra算法例题代码
Dijkstra算法function=minRoute()
% 网络拓扑结构
topo = [ 0,20,18,18,15, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf;
20, 0,26, inf,28, inf, inf, inf,30,28,30,30, inf, inf, inf, inf, inf, inf;
18,26, 0,20, inf, inf, inf, inf, inf, inf, inf,20, inf,26, inf, inf, inf, inf;
18, inf,20, 0,18,18,50, inf, inf, inf, inf, inf, inf, inf, inf,18, inf, inf;
15,18, inf,18, 0, inf,38,32, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf;
inf, inf, inf,18, inf, 0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,36;
inf, inf, inf,50,38, inf, 0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,34;
inf, inf, inf, inf,32, inf, inf, 0,36, inf, inf, inf, inf, inf, inf, inf, inf, inf;
inf,30, inf, inf, inf, inf, inf, inf, 0, inf, inf, inf, inf, inf, inf, inf, inf, inf;
inf,28, inf, inf, inf, inf, inf, inf, inf, 0,30, inf, inf, inf, inf, inf, inf, inf;
inf,30, inf, inf, inf, inf, inf, inf, inf,30, 0,26,32, inf, inf, inf, inf, inf;
inf,30,20, inf, inf, inf, inf, inf, inf, inf,26, 0,28, inf, inf, inf, inf, inf;
inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,32,28, 0,32, inf, inf, inf, inf;
inf, inf,26, inf, inf, inf, inf, inf, inf, inf, inf, inf,32, 0,34, inf, inf, inf;
inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,34, 0,24,36, inf;
inf, inf, inf,18, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,24, 0,30, inf;
inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf,36,30, 0,32;
inf, inf, inf, inf, inf,36,34, inf, inf, inf, inf, inf, inf, inf, inf, inf,32, 0;];
dij = ones(size(topo)) * inf; % 距离矩阵
pij = zeros(size(topo)); % 前一跳矩阵
nodeNum = size(topo, 1);
for nodeI = 1 : nodeNum
sourceNode = nodeI; % 源节点
dij(sourceNode , sourceNode) = 0; % 源节点到源节点的距离为0
s = []; % 已计算节点集合
q = 1 : nodeNum; % 未处理节点集合
qval = topo(sourceNode , :); % 源节点到未处理节点的单挑距离
while size(q , 2) > 0 % 对为处理的节点进行遍历
= sort(qval); % 选择最近节点
s(end+1) = q(1 , index(1)); % 加入已经处理节点集合
u = q(1 , index(1)); % 获得当前处理节点的id
for i = 1 : size(topo(u , :) , 2)
if topo(u , i) < inf % 考察u节点的所有直接连接节点
if dij(sourceNode , i) > dij(sourceNode , u) + topo(u , i)
% 如果源节点到u的距离加上u到i节点的距离要比源节点直接到i节点的距离近
% 则u应该出现在最短路径上 ， 跟新源节点到i节点的距离值
dij(sourceNode , i) = dij(sourceNode , u) + topo(u , i);
pij(sourceNode , i) = u;
end
end
end
q(index(1)) = []; % 从q和qval集合中移除u节点
% qval(index(1)) = []; % 没有更新待测节点的距离矩阵
qval = dij(sourceNode , q); % 修正！！！
end
end
% 将前一跳矩阵转换为下一跳矩阵
for i = 1 : nodeNum
for j = 1 : nodeNum
s = ;
temp = j;
if (pij(i , temp) > 0) % 10/11/2014修正
while temp ~= i
s(end + 1) = pij(i , temp);
temp = pij(i , temp);
end
temp = i;
for k = size(s , 2) - 1: -1 : 1
nij(temp , j) = s(1 , k);
temp = s(1 , k);
end
end
end
end
end
页:
[1]