第1页 / 共8页
第2页 / 共8页
第3页 / 共8页
第4页 / 共8页
第5页 / 共8页
第6页 / 共8页
第7页 / 共8页
第8页 / 共8页
图论极其运用的论文非常实用.doc
图论及其算法
应用 Floyd 算法解决物流中心选址问题
摘要：物流中心的选址问题是整个物流运输网络的关键所在，它涉及到运输路线的选择与规
划，而运输线路的长短直接影响着物流的费用。在分析物流网络的基础上，将图论中的弗洛
伊德（Floyd）算法应用于物流中心的选址上，以最少物流费用为最优目标。
关键词：最短路径 Floyd 算法 物流中心选址。
1、引 言
图论〔Graph Theory〕是数学的一个分支。它以图为研究对象。图论中的图是由若干给
定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的 某种特定关
系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。
在物流中心的选址问题中，点表示可供选择的配送中心，而其间的连线 (边) 则表示物
流费用．这种由顶点、边和某些数量指标组成的图，是客观世界的多层次、多结构、多序列
在人脑中的一种反映，能形象、清晰地描述空间中 的位置关系，可以定量处理许多问题．运
用图论中的有关理论和方法解决配送中心选址问题具有一定的实际意义。
本文采用了 Floyd 算法求解，介绍了该算法的基本思想和算法过程，阐述了 Flo3d 全部
顶点问最短路径算法选址的原理，并通过实例讨论了选址算法的步骤及 MATLAB 程序实
现的全过程．
2、最短路径算法的研究
解决最短路径问题就是运用图论的方法，现实中最短路问题有着很实际的应用。比如需
要架设电网、通信网络以及其他的有线网络，基于全网的考虑之下，点和点之间怎样架设一
条最短的线路就是一个实际的最短路问题。或者从某城市到另一个城市的最省路径也是一个
典型的最短路问题。按照图论的表述，在一个图中，两点之间的路径可能有很多条，且每条
路径所经过的边数可能是不同的，如果是网络，每条路径的各边权数之和也可能是不同的，
怎样找到一条顶点对顶点之间的各边权数之和为最小的路径问题称为最短路问题[6]。
图论中的最短路径算法有两种：一种是求从某一点至其他各点之间最短距离的 Dijkstra
算法；另一种是求全部顶点间最短路径的 Floyd 算法。Dijkstra 算法是针对运输合理化的问
题，而 Floyd 算法则主要针对如何选择合理的物流中心、使总运输费用最小的问题。因此，
本文主要是用 Floyd 算法解决物流中心的选址问题。
1
图论及其算法
2.1 Floyd 算法的基本思
]21[ 、想
Floyd 算法的基本思想是从任意 2 个顶点 iv 到 jv 的距离的带权邻接矩阵开始，每次插
入一个顶点 kv ，然后将 iv 到 jv 间的已知最短路径与插入顶点 kv 作为中间顶点时可能产生
的 iv 到 jv 路径距离比较，取较小值以得到新的距离矩阵．如此循环迭代下去，依次构造出
门个矩阵 )1(D ,
)2(D ,…… (n)D ，当所有的顶点均作为任意 2 个顶点 iv 到 jv 中间顶点时得到
的最后的带权邻接矩阵 (n)D 就反映了所有顶点对之间的最短距离信息，成为图 G 的距离矩
阵．
2.2 构造图 G 的距离矩 ]2[阵
设 G 是 n 个顶点的图，且其顶点用从 1 到 n 的整数编号。
（1）把 G 的带权邻接矩阵 D 作为距离矩阵的初值，即 )0(D =
)0(
)（
ijd
=D。当两点之间
*
nn
有边时， )0(
ijd 等于边的权；当两点之间没有边时， )0(
ijd 记为无穷大；当 i=j 时， )0(
ijd
=0.
（2）构造 )1(D =
)1( )（
ijd
，其中 )1(
ijd
=min（ )0(
ijd ， )0(
ijd
+
)0(ijd
）是从 iv 到 jv 的只允许
*
nn
以 1v 作为中间点的路径中最短路的长度。
（3）继续构造 (k)D ，其中 2≤k≤n，其中 )
(k
ijd
=min（
)1
( k
ijd ，
)1
( k
ikd
+
)1
( k
kjd ）是从 iv 到
jv 的只允许以 1v 、 2v 、…… kv 作为中间点的路径中最短路的长度。
（4）这时图 G 的距离矩阵 )(nD 已经构造出来。
3、在物流中心选址的应用
在某城市建立物流配送网络，包含八个地方，则可将物流配送网络简化为有 8 个顶点的
图，各点之间的物流费用如图所示，试对该物流配送网络选择最佳的物流中心。
2
图论及其算法
3.1 物流中心选址的算 ]3[法
图 1.物流网络
（1）、运用 Floyd 算法构造距离矩阵 (n)D ，其中 d(i,j)表示 i 到 j 的最短距离。
①输入带权邻接矩阵 W，赋初值：对所有 i，j,d(i,)j w(i,j),r(i,j) j,k 1;
②更新 d(i,j),r(i,j)：对所有 i，j，若 d(i,j)+d(i,k)
图论及其算法
①赋初值：minC 0，minK 1，k 1，
② 更 新 最 小 费 用 minC ， 并 确 定 最 优 顶 点 minK ： 对 所 有 k, 若 C(k)<=minC ， 则
minC C(k),minK k；
③若 ki=n，停止，否则 k k+1,转②。
3.2 运用 MATLAB 实现选址算
]54[ 、法
物流中心选址的 MATLAB 程序见附录。
3.2.1 程序运行结果
6
0
inf 8
inf 2
3
0
4
初始矩阵 )0(D 为：
inf 13 6
w=[0
5
6
9
inf inf 0
4
8
3
2
9
inf 5
0
13 7
inf inf 10
6
inf 5
inf inf inf 0
inf 12
inf 7
inf 8
inf;
inf;
inf 5;
7
inf 12
inf inf 7;
10 inf inf;
0
inf 8;
inf;
inf 0];
w_(:,:,1) =
0
6
Inf
8
Inf
13
6
Inf
0
6
Inf
8
11
13
6
11
w_(:,:,2) =
6
0
Inf
2
5
7
12
5
6
0
Inf
2
5
7
12
5
Inf
Inf
0
3
9
Inf
12
Inf
Inf
Inf
0
3
9
Inf
12
Inf
8
2
3
0
4
21
14
7
8
2
3
0
4
9
14
7
Inf
5
9
4
0
10
Inf
Inf
13
7
Inf
21
10
0
19
8
6
12
12
14
Inf
19
0
Inf
Inf
Inf
5
7
Inf
8
Inf
0
11
5
9
4
0
10
17
10
13
7
Inf
6
12
12
11
5
Inf
9
10
0
19
8
14
17
19
0
17
7
10
8
17
0
w_(:,:,3) =
0
6
Inf
8
11
13
6
11
4
0
Inf
6
Inf
8
11
13
6
11
2
5
7
12
5
6
0
5
2
5
7
12
5
6
0
5
2
5
7
12
5
6
0
5
2
5
7
12
5
6
0
5
2
5
w_(:,:,4) =
0
6
11
8
11
13
6
11
w_(:,:,5) =
0
6
11
8
11
13
6
11
w_(:,:,6) =
0
6
11
8
11
13
6
11
w_(:,:,7) =
0
6
11
8
11
Inf
0
3
9
Inf
12
Inf
11
5
0
3
7
12
12
10
11
5
0
3
7
12
12
10
11
5
0
3
7
12
12
10
11
5
0
3
7
2
3
0
4
9
14
7
8
2
3
0
4
9
14
7
8
2
3
0
4
9
14
7
8
2
3
0
4
9
14
7
8
2
3
0
4
5
9
4
0
10
17
10
11
5
7
4
0
10
17
10
11
5
7
4
0
10
17
10
11
5
7
4
0
10
17
10
11
5
7
4
0
图论及其算法
7
Inf
12
12
Inf
9
10
0
19
8
13
7
12
9
10
0
19
8
13
7
12
9
10
0
19
8
13
7
12
9
10
0
19
8
13
7
12
9
10
14
17
19
0
17
6
12
12
14
17
19
0
17
6
12
12
14
17
19
0
17
6
12
12
14
17
19
0
17
6
12
12
14
17
5
5
7
10
8
17
0
11
5
10
7
10
8
17
0
11
5
10
7
10
8
17
0
11
5
10
7
10
8
17
0
11
5
10
7
10
图论及其算法
9
14
7
8
2
3
0
4
9
14
7
10
17
10
11
5
7
4
0
10
17
10
0
19
8
13
7
12
9
10
0
19
8
19
0
17
6
12
12
14
17
19
0
17
8
17
0
11
5
10
7
10
8
17
0
12
12
10
11
5
0
3
7
12
12
10
7
12
5
6
0
5
2
5
7
12
5
13
6
11
w_(:,:,8) =
0
6
11
8
11
13
6
11
result =
66
42
60
47
64
78
97
68
m =
42
图 2
iv 到其他各点的物流费用的总和的比较图
6
图论及其算法
3.2.2 运行结果分析
经 过 程 序 运 行 求 出 了 iv 到 其 他 各 点 的 物 流 费 用 和 为 C(
1v )=66, C(
2v )=42,
C(
3v )=60,C(
4v )=47, C(
5v )=64, C(
6v )=78C(
7v )=,97,C(
8v )=68.比较可知， 1v 到其他各点的费
用最小。因此， 1v 点选为物流中心是最优的。
4．结 论
Floyd 最短路径算法是用矩阵的思想来解决任意两点之间的最短距离。它最重要也最明
显的应用就是在多个地址中找到一个合理的物流中心，从一个图的距离矩阵中可以得到的结
论有：任意两点之间的最短距离，两点之间达到最短距离的时候应该走的路径。Floyd 算法
在物流运输中的应用，能够降低成本，优化物流网络。
参考文献：
【1】 赵 静，但 琦．数学建模与数学实验【M】．北京：高等教育出版社，2000．
【2】 马杰良，李鑫丽，王玉珏，基于图论的物流管理一体化，2007．
【3】 刘 琛．计算机算法引论——设计与分析技术【M】．北京：科学出版社，2003．
【4】 张宜华、精边 MATLAB5【M】．北京：清华大学出版社，l999．
【5】 王沫然．MATLAB6．0 与科学计算机【M】．北京：北京电子与工业出版社 ，2001．
【6】 殷剑宏 吴开亚著 图论及其算法. 【M】．合肥：中国科学技术大学出版社，2003.7
◆ 附 录
6
0
inf; %初始矩阵
物流中心选址程序源代码
clear;
clc;
inf 13 6
w=[0
5
6
9
inf inf 0
4
3
8
2
9
inf 5
0
inf inf 10
13 7
6
inf 5
inf 8
inf 2
3
0
4
inf inf inf 0
inf 12
inf 7
inf 8
inf;
inf 5;
7
inf 12
inf inf 7;
10 inf inf;
0
inf 8;
inf;
inf 0];
[a,a]=size(w); %初始矩阵的大小
for k=1:a
w_(:,:,k)=w;
7
图论及其算法
if w_(i,j,k)>=w(i,k)+w(k,j)
w_(i,j,k)=w(i,k)+w(k,j);
%如果两点间距离大于w(i,1)+w(1,j),将后者取值赋给前者
end
end
k=1;
for i=1:a
for j=1:a
end
end
for k=2:a
w_(:,:,k)=w_(:,:,k-1);
for i=1:a
for j=1:a
if w_(i,j,k)>=w_(i,k,k-1)+w_(k,j,k-1)
w_(i,j,k)=w_(i,k,k-1)+w_(k,j,k-1);
%只允许以1、2……k-1作为中间点的路径中最短的路径
end
end
end
end
w_
k=a;
result=zeros(1,a);
result=(sum(w_(:,:,k),2)).' %对其进行行向量相加，为求出各行之和的最小值做准备
i=1:a;
stem(i,result) %画图，通过图形可以得到各行之和的最小值
axis([0,9,0,110]);
m=min(result)
%该值为最佳配送值
8
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
