- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
将A[1][0]改为6；存在路径v1-v3-v2,长 度为3,比原长度短,将A[1][2]改为3；
将path[0][2]、path[1][0]后path[1][2]
初始时,有A-1[i][j]=cost[i][j]。当求从顶点vi到顶点 vj的路径上所经过的顶点编号不大于k+1的最短路径长 度时,要分两种情况考虑：
一种情况是该路径不经过顶点编号为k+1的顶点, 此时该路径长度与从顶点vi到顶点vj的路径上所经过的 顶点编号不大于k的最短路径长度相同；
另一种情况是从顶点vi到顶点vj的最短路径上经过 编号为k+1的顶点。
{ int i;
for (i=0;i<n;i++)
if (s[i]==1)
{ printf(“从%d到%d的最短路径长度为:
%d\t路径为:",v0,i,dist[i]);
printf("%d,",v0);
/*输出路径上的起点*/
Ppath(path,i,v0);
/*输出路径上的中间点*/
printf("%d\n",i);
➢ 最小生成树问题
➢ 连线问题—欲修筑连接多个城市的铁路设计一个线路图， 使总造价最低（prim算法、Kruskal算法 ）
➢ 图的匹配问题
➢ 人员分派问题：n个工作人员去做n份工作，每人适合做
其中一份或几份，问能否每人都有一份适合的工作？如果 不能，最多几人可以有适合的工作？(匈牙利算法)
➢ 遍历性问题
{2,3,4,5,6}
{0,4,5,6,11,∞,∞}
{3,4,5,6}
{0,4,5,6,11,9,∞}
{4,5,6}
{0,4,5,6,11,9,19}
{4,6}
{0,4,5,6,10,9,17}
{6}
{0,4,5,6,10,9,16}
{}
{0,4,5,6,10,9,16}
则v0到v1～v6各顶点的最短距离分别为4、5、6、 10、9和16。
/*距离初始化*/
s[i]=0;
/*s[]置空*/
if (cost[v0][i]<INF)
/*路径初始化*/
path[i]=v0;
else
path[i]=-1;
}
s[v0]=1;path[v0]=0; /*源点编号v0放入s中*/
for (i=0;i<n;i++) /*循环直到所有顶点的最短路径都求出*/
{ mindis=INF;
u=-1;
for (j=0;j<n;j++) /*选取不在s中且具有最小距离的顶点u*/
if (s[j]==0 && dist[j]<mindis)
{ u=j; mindis=dist[j]; }
s[u]=1;
/*顶点u加入s中*/
for (j=0;j<n;j++) /*修改不在s中的顶点的距离*/
狄克斯特拉算法如下(n为图G的顶点数,v0为源点编号)：
void Dijkstra(int cost[][MAXV],int n,int v0)
{ int dist[MAXV],path[MAXV]; int s[MAXV];int mindis,i,j,u;
for (i=0;i<n;i++)
{ dist[i]=cost[v0][i];
我们介绍三种优化模型：
图论 动态优化 排队论
重点：图论模型的数学建模案例分析
数学建模的方法和步骤 基本方法
根据对客观事物特性的认识， •机理分析 找出反映内部机理的数量规律 •测试分析 将研究对象看作“黑箱”,通过对量测数据
的统计分析，找出与数据拟合最好的模型
•二者结合 机理分析建立模型结构,测试分析确定模型参数
➢ 中国邮递员问题—邮递员发送邮件时，要从 邮局出发，经过他投递范围内的每条街道至 少一次，然后返回邮局，但邮递员希望选择 一条行程最短的路线
➢ 最小费用最大流问题
➢ 在运输问题中，人们总是希望在完成运输任 务的同时，寻求一个使总的运输费用最小的 运输方案
1、最短路问题
（1） 基 本 概 念 （2）固 定 起 点 的 最 短 路 （3）每 对 顶 点 之 间 的 最 短 路
{ int k;
k=path[i];
if (k==v0) return;
/*找到了起点则返回*/
Ppath(path,k,v0);
/*找k顶点的前一个顶点*/
printf("%d,",k); /*输出k顶点*/
}
void Dispath(int dist[],int path[],int s[],int n,int v0)
(4)重复步骤(2)和(3)直到所有顶点都包含在S中。
S {0} {0,1} {0,1,2} {0,1,2,3} {0,1,2,3,5} {0,1,2,3,5,4} {0,1,2,3,5,4,6}
1
7
4
16
6 0
2
6
4 2
3 5
U
4
6
1
6
8 5
v0到0～6各顶点的距离
{1,2,3,4,5,6} {0,4,6,6,∞,∞,∞}
从一个顶点到其余各顶点的最短路径
问 题：给定一个带权有向图G与源点v,求从v 到G中其他顶点的最短 路径,并限定各边上的权值 大于或等于0。
采用狄克斯特拉(Dijkstra)算法求解 基本思想是：设G=(V,E)是一个带权有向图, 把图中 顶点集合V分成两组： 第一组为已求出最短路径的顶点集合(用S表示,初始 时将结束Svk中加了只入) 有到一集个合源S点中,,以直后到每全求部得顶一点条都最加短入到路S径中v,,…算v法k,就就 第二组为其余未确定最短 路径的顶点集合(用U表 示)。 按最短 路径长度的递增次序依次把第二组的顶点 加入S中。在加入的过程中,总保持从源点v到S中各顶点 的最短路径长度不大于从源点v到U中任何顶点的最短 路径长度。此外,每个顶点对应一个距离,S中的顶点的 距离就是从v到此顶点的最短 路径长度,U中的顶点的距 离从v到此顶点只包括S中的顶点为中间顶点的当前最 短 路径长度。
基本概念
定 义 １ 在 无 向 图 G = (V ,E , )中 ： （ １ ） 顶 点 与 边 相 互 交 错 且 (e i) v i 1 v i (i= 1 ,2 ,… k )的 有 限 非 空 序 列 w (v 0 e 1 v 1 e 2 v k 1 e kv k)称 为 一 条 从 v 0到 v k的 通 路 ， 记 为 W v 0 v k （ ２ ） 边 不 重 复 但 顶 点 可 重 复 的 通 路 称 为 道 路 ， 记 为 T v 0 v k （ ３ ） 边 与 顶 点 均 不 重 复 的 通 路 称 为 路 径 ， 记 为 P v 0 v k
数学建模的一般步骤
模型准备
模型假设
模型构成
模型检验
模型分析
模型求解
模型应用
一、图论方法
➢ 最短路问题
➢ 两个指定顶点之间的最短路径—给出了一个连接若干个 城镇的铁路网络，在这个网络的两个指定城镇间，找一条 最短铁路线 （Dijkstra算法 ）
➢ 每对顶点之间的最短路径 （Dijkstra算法、Floyd算法 ）
假设有向图G=(V,E)采用邻接矩阵cost存储,另外
设置一个二维数组A用于存放当前顶点之间的最短路
径长度,分量A[i][j]表示当前顶点vi到顶点vj的最短路 径长度。弗洛伊德算法的基本思想是递推产生一个矩
阵序列A0,A1,…,Ak,…,An,其中Ak[i][j]表示从顶点vi到 顶点vj的路径上所经过的顶点编号不大于k的最短路 径长度。
0
5
7
34
2 2
1
3
2
3
1
0 5 7
0
4
2
3 3 0 2
1
0
0 5 7 A 1 0 4 2
3 3 0 2 1 0
1 1 1 1 Path 1 1 1 1 1
1 1 1 1 1 1 1 1
采用弗洛伊德算法求解过程
考虑顶点v0,A0[i][j]表示由vi到vj, 经由顶点v0的最短路径。只有从v2到 v1经过v0的路径和从v2到v3经过v0的 路径,不影响v2到v1和v2到v3的路径长 度,因此,有：
path[1][0]均改为2。因此,有：
0
5
7
34
2 2
1
3
2
3
1
0 5 9 7
A2
7
0
4
2
3 3 0 2
4
4
1
0
1 1 1 1
Path2
2
1 1 1
1 1 1 1
2
2 1 1
考虑顶点v3,A3[i][j]表示由vi到vj, 经由顶点v3的最短路径。存在路径v0v3-v2,长度为8比原长度短,将A[0][2]改 为8；存在路径v1-v3-v2-v0,长度为 6(A[1][3]+A[3][0]=2+4=6)比原长度短,
因此,有：
0
5
7
34
2 2
1
3
2
3
1
0 5 9 7
1 1 1 1
A 1 3
0 3
4 0
2
2
Path1 1 1 1 1 1 1 1 1
1
0
1 1 1 1
考虑顶点v2,A2[i][j]表示由vi到vj,经由 顶点v2的最短路径。存在路径v3-v2v0,长度为4,将A[3][0]改为4；存在路 径v3-v2-v1,长度为4,将A[3][1]改为4。 存在路径v1-v2-v0,长度为7,将A[1][0] 改为7。将path[3][0]、path[3][1]和
