|
preNode=Dijkstra(totalNodes,nodeDistance,routeStops,startPoint,endPoint);
totalNodes 网络总节点数
nodeDistance 网络节点距离表
routeStops 遍历的访问客户点
startPoint 起始点
endPoint 结束点
函数的目的是从起始点出发startPoint ,访问routeStops 的全部点,到达endPoint ,可以用来求解旅行商问题,当startPoint =endPoint 时
主要代码如下:
------------------------------------------------------------------------------------------
function preNode=Dijkstra(totalNodes,nodeDistance,routeStops,startPoint,endPoint);
% totalNodes
% routeStops
% startPoint
% endPoint
%totalNodes->起点 终点 和 候选节点 的数量 即 nodeDistance的行和列 数
global NumberofCandidate
n=size(routeStops,2);
distance(1:totalNodes)=1000000;
preNode(1:n)=-1;
markedNodes(1:n)=-1;
distance(startPoint)=0;
currentNode=startPoint;
adjacentNodes=FindAdjacentNodes(routeStops,markedNodes);%未标记的点,即需要搜索的点
sizeOfAdjacentNodes=size(adjacentNodes,2);
while sizeOfAdjacentNodes>=1
temp=0;
for i=1:sizeOfAdjacentNodes
% currentNode
% adjacentNodes(i)
if distance(currentNode)+nodeDistance(currentNode,adjacentNodes(i))+nodeDistance(adjacentNodes(i),endPoint)<distance(adjacentNodes(i))
distance(adjacentNodes(i))=distance(currentNode)+nodeDistance(currentNode,adjacentNodes(i))+nodeDistance(adjacentNodes(i),endPoint);
end
temp(i)=distance(adjacentNodes(i));
end
%------------------------------------------------------------------
[minValue,index]=min(temp);
preNode(ReturnOrderElementInSet(routeStops,adjacentNodes(index)))=currentNode;%%%%%%%%%%%%%%%%%%%%%%%%
markedNodes=MakeNodeTags(markedNodes,routeStops,adjacentNodes(index));%标记语言
currentNode=adjacentNodes(index);%标记
adjacentNodes=FindAdjacentNodes(routeStops,markedNodes);
sizeOfAdjacentNodes=size(adjacentNodes,2);
end
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-9-27 09:31
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社