12 / 2 页

楼主: 珊珊魏

用lingo求解最短路径求代码

[复制链接]

字体大小: 正常放大

Valentiner

1 主题	9 听众	512 积分

升级 70.67%

TA的每日心情

	奋斗 2016-7-11 18:46

签到天数: 201 天

[LV.7]常住居民III

11^#

发表于 2013-4-29 08:35 |只看该作者

|招呼Ta 关注Ta

你是从哪儿到哪儿啊

点评

珊珊魏你刷我屏坏人详情回复发表于 2013-5-17 15:17

我也说一句

发表

使用道具举报

zhangc_ningbo

26 主题	10 听众	562 积分

升级 87.33%

TA的每日心情

	开心 2015-5-2 15:22

签到天数: 174 天

[LV.7]常住居民III

自我介绍: 自信

群组: 学术交流B

群组: 学术交流A

12^#

发表于 2013-4-29 11:57 |只看该作者 |招呼Ta 关注Ta

这是用MATLAB做的
% 两点间最短路的 Dijkstra 算法
function [d index1 index2] = Dijkf(a)
% a表示图的权值矩阵
% b表示所有最短路的权和
% index1表示标号顶点顺序
% index2表示标号顶点索引

% 参数初始化
M = max(max(a));
pb(1:length(a)) = 0;
pb(1) = 1;
index1 = 1;
index2 = ones(1,length(a));
d(1:length(a)) = M;d(1) = 0;temp = 1;
% 更新l(v)，同时记录顶点顺序和顶点索引
while sum(pb) < length(a)
tb = find(pb == 0);
d(tb) = min(d(tb),d(temp)+a(temp,tb));
tmpb = find(d(tb) == min(d(tb)));
temp = tb(tmpb(1));
pb(temp) = 1;
index1 = [index1,temp]; % 记录标号顺序
index = index1(find(d(index1) == d(temp) a(temp,index1)));
if length(index) >= 2
index = index(1);
end
index2(temp) = index; % 记录标号索引
end
d;
index1;
index2;