科学网基于Dijkstra的双源最短路算法
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);
同类文章排行
- 2019年广东公务员考试面试热点练习(62)
- 2019年广东公务员考试面试热点练习(57)
- 津巴布韦总理称上周车祸是意外
- 持居留条回国 旅游千万不要打擦边球
- 英国计划斥资4000万镑帮白领找工作
- 王健林又悄悄卖了几家万达广场!保险、信托接
- 2019年深圳公务员考试公告
- 俄罗斯醉酒外交官在飞机上与人打架迫使飞机返
- 2019年广东公务员考试面试热点练习(56)
- 2020年广东公务员面试模拟题:大学生贷款享受优惠政策
最新资讯文章
- 梅德韦杰夫承认俄罗斯经济被危机重创
- 伊朗又试射了一枚远程导弹
- 朝鲜最高司令部要求做好一切战斗准备
- 持居留条回国 旅游千万不要打擦边球
- “外交为民”新举措 罗马地区侨团联络会正式成
- 以色列称伊朗已跨越核武技术门坎
- 美军文件公开宣称以色列为有核国家
- 俄罗斯专家称中国应向北约开放瓦罕走廊
- 伊拉克发生自杀式袭击28人死亡57人受伤
- 关塔那摩囚犯称英军情五处串通CIA对其酷刑
- 奥地利兽父案下周开审 乱伦父刑期或少于10年
- 苏丹总统:决不向殖民主义和国际刑事法院屈服
- 朝鲜切断朝韩陆路通行线 620名韩国人被困当地
- 日本首相麻生再次表示美国对钓鱼岛立场没变
- 委内瑞拉将建立人民公社大食堂
- 马达加斯加军营哗变 士兵拒绝向民众开枪(组图
- 美韩展开12天联合军演 7艘宙斯盾舰参加
- 日本发明新型遥控器 脸部肌肉可遥控家电(图)
- 英国计划斥资4000万镑帮白领找工作
- 世行报告称全球经济将现二战后首“负”