数学建模社区-数学中国

标题: 用lingo求解最短路径求代码 [打印本页]

作者: 珊珊魏 时间: 2013-4-28 16:09
标题: 用lingo求解最短路径求代码
设6个城市之间的一个公路网(图1)每条公路为图中的边,边上的权数表示该段公路的长度(单位:百公里),设你处在城市 ,那么从到应选择哪一路径使你的费用最省。

clip_image002.jpg (30.33 KB, 下载次数: 153)

作者: Valentiner 时间: 2013-4-29 08:34
你是从哪儿到哪儿啊

作者: Valentiner 时间: 2013-4-29 08:35
你是从哪儿到哪儿啊

作者: zhangc_ningbo 时间: 2013-4-29 11:57
这是用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;

作者: 珊珊魏 时间: 2013-5-17 15:17

Valentiner 发表于 2013-4-29 08:35
你是从哪儿到哪儿啊

你刷我屏坏人

作者: 珊珊魏 时间: 2013-5-17 15:17

zhangc_ningbo 发表于 2013-4-29 11:57
这是用MATLAB做的
% 两点间最短路的 Dijkstra 算法
function [d index1 index2] = Dijkf(a)

O(∩_∩)O谢谢谢谢

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)