以上程序是通用程序，只需输入初始距离矩 阵，就能输出最短路矩阵以及最短路的路径矩阵， 将程序以文件名floyd.m存盘。
例1 以2007年研究生数学建模竞赛C题为例， 已知16个邮政支局的初始距离矩阵，求任意两个 节点之间的最短路。
解：编写主程序如下：
a=[0, 27, 44, 17, 11, 27, 42, inf, inf, inf, 20, 25, 21, 21, 18, 27, inf;
…………………………………………
inf,inf,inf,inf,30,inf,inf,inf,21,13,20,inf,inf,inf,in f,9,0]; [D,R]=floyd(a);
输入数据中的inf表示无穷大（两个顶点之间 没有边直接相连）。
在图中，两个顶点u和v之间由顶点和边构成 的交错序列（使u和v相通）称为链（通道），没 有重复边的通道称为迹，起点与终点重合的通道 称为闭通道，不重合的称为开通道，没有重复顶 点（必然边也不重复）的开通道称为路，起点与 终点重合的路称为圈（回路）．包含奇数个顶点 （或边）的圈称为奇圈，包含偶数个顶点（或边） 的圈称为偶圈。如果顶点u和v之间存在一条路， 则称u和v是连通的，任意两个顶点都连通的图称 为连通图．无圈的连通图称为树，如果一棵树T 包含了图G的所有顶点，称T为G的生成树．
用 V={v1,v2,…} 表 示 全 体 顶 点 的 集 合 ， 用 E={e1,e2,…} 表示全体边的集合，如果对于E中的 任一条边ek，在V中都有一对顶点(vi,vj)和它对应， 则称由V和E组成的集体为一个图，记为G={V,E}， 简写为G．
二、基本概念
点与边相连接称为关联，与边e关联的顶点称为 该边的端点，与同一条边关联的两个顶点称为相 邻顶点，与同一个顶点关联的边称为相邻边．具 有相同顶点的边称为平行边，两个端点重合的边 称为环．所有线段都没有方向的图称为无向图， 所有线段都有方向的图称为有向图，既称为简单图，任意两个顶点之间都有一条 边相连的简单图称为完全图．任意两个顶点之间 有且只有一条弧相连的有向图称为竞赛图．
for j=1:n R(i,j)=j;
end end
for k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)<D(i,j) D(i,j)=D(i,k)+D(k,j); %在循环中进
行矩阵迭代 R(i,j)=R(i,k); % R是路径矩阵
end end end end D,R %输出最短路矩阵和最短路的路径矩阵。
d (1) ij
min
{di(j0)
,
d (0) i1
d (0) 1j
}
,
i
j
上式表示dij(1)在dij(0)以及从顶点vi经过顶点v1到 vj的权之和di1(0)+d1j(0)两者之中选择最短长度。依 此规则迭代。
d (2) ij
min
{di(j1)
,
d (1) i2
d (1) 2j
}
,
i
j
上式表示dij(2)在dij(1)以及从顶点vi经过顶点v2到 vj的权之和di2(1)+d2j(1)两者之中选择最短长度。依 此类推，迭代公式为 ：
图论中几个典型 问题的求解
§1 图的基本概念
图是一种直观形象地描述已知信息的方 式，它使事物之间的关系简洁明了，是分 析问题的有用工具，很多实际问题可以用 图来描述。
一、图的定义
图论是以图为研究对象的数学分支，在图论 中，图由一些点和点之间的连线所组成．
称图中的点为顶点（节点），称连接顶点的 没有方向的线段为边，称有方向的线段为弧．
d (m) ij
min
{di(jm1)
,
d (m1) im
d (m11) mj
}
,
i
j
上式表示dij(m)在dij(m-1)以及从顶点vi经过顶点vm 到vj的权之和dim(m-1)+dmj(m-1)两者之中选择最短长 度。当m=n时结束迭代。
2．程序设计 先编写Flody算法的子程序（函数）如下： Function [D,R]=floyd(a) n=size(a,1); D=a; % D是初始矩阵 for i=1:n
1．算法原理
设A=[aij]m×n是图的权矩阵（也称带权邻接矩 阵），其中aij是图上连接顶点i和j的边的权，如 果两顶点之间没有直接相连的边（即两顶点不相 邻），则aij=∞。
令矩阵D(0)=A，作为迭代的初始矩阵，从它出 发按照一定规则求D(1)，又由D(1)按照类似的规则 求D(2)，依此类推进行迭代直至求出D(n)，设矩阵 D(m)的元素为dij(m)，迭代规则为：
一、最短路的概念
给定一个连通的赋权图G={V,E}，设R是连接 节点vi和vj的一条路，该路的权定义为路中所有 各边权之和，如果路R在所有连接节点vi和vj的路 中权最小，则称它为vi和vj间的最短路。
二、任意两点之间的最短路(Floyd算法) Floyd算法利用距离矩阵进行迭代运算，可以 一次性地求出任意两点之间的最短路，该方法的 思路有创意，计算量小，编程较简单，又称矩阵 求解法。
如果图G的每条边e都对应一个实数C(e)，称 C(e)为该边e的权，称图G为赋权图．通常称赋权 的有向图为网络．
v4
e9
e4
v2
e1
e5
v5
e10
v1
e3
e2
e6
e8
e11
v7
v3
e7
v6
图中边e6和e7是平行边，e9是环，顶点v4是悬 挂点，边e4是悬挂边．
§2 最短路问题
最短路问题是图论应用的基础，很多实际问 题，如线路的布设、运输规划、运输网络最小费 用流等问题，都可以通过建立最短路模型来求解。 有些有深度的图与网络优化问题，如旅行售货商、 中国邮递员等问题，需要在首先求出任意两点之 间最短路的基础上解决。
在无向图中与顶点v关联的边的数目（环算两 次）称为该顶点的度（或次数），记为d(v)。度 为奇数的顶点叫做奇点，度为偶数的顶点叫做偶
点。在有向图中，从顶点v引出的边的数目称为 该顶点的出度，记为d+(v)，从顶点v引入的边的 数 目 称为 该 顶点 的 入度 ， 记为 d-(v)， 而 d(v) ＝ d+(v)+d-(v)称为v的次数。