数学建模任意两点间的最短路

任意两点间最短距离-floyd算法matlab程序

%Floyd's Algorithm 通过一个图的权值矩阵求出它的任意两点间的最短路径矩阵。 %Floyd算法适用于APSP(All Pairs Shortest Paths)，是一种动态规划算法， %稠密图效果最佳，边权可正可负。

%此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

%a为图的带权邻接矩阵

%从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新， %即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)； %又用同样地公式由D(1)构造出D(2)；……； %最后又用同样的公式由D(n-1)构造出矩阵D(n)。

%矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，

%同时还可引入一个后继节点矩阵path来记录两点间的最短路径。

%采用的是松弛技术，对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

matlab函数文件为：

function [D,path]=floyd1(a) a(find(a==0))=inf;

n=size(a,1

效果展示：

开头输入的是点的序列号（表示第几个点），显示的是最短路径的走法（同样以点的序列号显示，表示途径的第几个点）。

%编写m文件

function [distance,path]=dijkstra(A,s,e) % [DISTANCE,PATH]=DIJKSTRA(A,S,E)

% returns the distance and path between the start node and the end node. %

% A: adjcent matrix % s: start node % e: end node

% initialize

n=size(A,1); % node number

D=A(s,:); % distance vector path=[]; % path vector visit=ones(1,n); % node visibility

visit(s)=0; % source node is unvisible parent=zeros(1,n); % parent node

% the shortest distan

交巡警服务平台的设置与调度

摘要

本论文主要是关于图论中的“最短路径问题”和“最优搜索问题”。问题所述的模型已经很自然地用图表示出来，所以我们运用图的性质和算法来求解问题。

图论中求最短路径通常采用dijkstra算法，但本题涉及的交巡警平台数量较多，即求多个源点到其它所有顶点的距离，所以采用floyd算法求解比较简单，其基本思想是通过程序得到每个节点到其他节点的最优距离。

针对问题一，用floyd算法算出每个交巡警平台3分钟内所能到达的全部节点，这些节点就是平台的管辖范围，但仍有3分钟内不能到达的节点，这些节点处就应该增设交巡警服务平台。在快速封锁13条交通要道时，要遵循封锁时间最短、每个平台的警力最多封锁一个路口的原则，运用LINGO程序解答。最后分析得到出警时间至少大于3分钟的节点，及工作量最大的平台，在这些节点处需要增加3个服务平台。

针对问题二，需要对发案率进行降序排列，筛选出发案率较高，但是未设置交巡警服务平台的节点。根据六个城区的基本数据，得到每个平台管辖的面积和人口，比较各平台的工作量，从而找出不合理的理由。在搜捕犯罪嫌疑人时要遵循两个原则：搜捕时间最短和围堵区域最小。根据逃犯的位置和逃跑的可能路径建立关于时间T的目标函数和初

灾情巡视路线的数学模型

摘 要

本文研究的是根据某县的乡（镇）、村公路网示意图，如何在不同条件下制定出最佳灾情巡视方案的问题。

针对问题一：首先将公路网转化为一张无向赋权图并构造其邻接矩阵，然后根据Dijkstra算法求出任意两点间的最短距离及O点到其余顶点的最短路，最短路构成了一棵以O为树根的最小生成树，将干枝分为三组，每组各顶点间的最短路构成一个完备加权图，再建立混合整数规划模型求其最佳H圈。再逐步调整，使三组中路程较长者减小，最后得到三个组路程分别为204.9km、208.8km和205.3km，最长路程为208.8km，路程均衡度为1.9%，总路程为619km。

针对问题二:依题意至少需要4组，根据问题一中得到的最小生成树将顶点分为4组，利用问题一中的算法，求出每组的最佳H圈，然后逐步调整，使四组中用时较长者减小，最后得到四个组所用时间分别为21.9h、22.41h、22.12h和21.66h，最长时间为22.41h，时间均衡度为3.3%。

针对问题三:根据O点到最远点的距离确定时间上界，然后根据时间上界和到O点的距离由远及近确定最优巡视路线，得最优方案为分23组，巡视时间为6.43h，具体路径见问题三解答。

针对问题四：以

例谈地球表面两点之间的最短航线问题

贵州省遵义市第二中学 梅永华 563000 电话：15985260788

地球是一个两极部位略扁的不规则球体,但在讨论两点之间的最短航线时,一般近视地认为地球是一个正球体,即在地球表面上两地之间的最短距离（或航线）应指的是经过这两点的球大圆在这两点间的一段劣弧长度,但这个圆的圆心必须经过球心(即地心)。 在中学地理应试中主要有以下几种情况:

1、晨昏线上两点之间的最短距离是该晨昏线上两点之间的劣弧部分。如图1右图中的的阴影部分为黑夜,GH之间的最短航线是沿着晨昏线的劣弧走：先东南，再向正东，后东北，即经过GMH,而不是GYH。

2、赤道上两点之间的最短距离是赤道上两点之间的劣弧部分。如图1左图中的AB之间的最短航线：A到B走为正东或B到A走为正西 。

3、经线上两点之间的最短距离是该经线上两点之间劣弧部分。如图1左图中的CD之间的最短航线：C到D为正北或D到A为正南。

4、若两地间的经度差等于180°，则经过两点的

大圆一定是经线圈。这两点间的最短航程须经过极点，其结果只能是先正北后正南或先正南后正北。 ⑴、同位于北半球的两点，最短航线必须经过北

极点，其航行方向一定是先向正北，过北极点后再向正南。

【课题】8．1 两点间的距离公式及中点公式

【教材说明】

本人所用教材为江苏教育出版社，凤凰职教《数学·第二册》。平面解析是用代数方法研究平面几何问题的学科，第八章《直线与圆的方程》属于平面解析几何学的基础知识。它侧重于数形结合的方法和形象思维的特征，综合了平面几何、代数、三角等知识。

【学情分析】

学生是一年级数控中专班，上课不能长时间集中注意力，计算能力不强，对抽象的知识理解能力不强，但是对直观的事物能够理解，对新事物也有较强的接受能力。

【教学目标】

知识目标：

1. 了解平面直角坐标系中的距离公式和中点公式的推导过程．

2. 掌握两点间的距离公式与中点坐标公式．

能力目标：

用“数形结合”的方法，介绍两个公式．培养学生解决问题的能力与计算能力．

情感目标：

通过观察、对比体会数学的对称美和谐美，培养学生的思考能力，学会从已有知识出发主动探索未知世界的意识及对待新知识的良好情感态度．

【教学重点】

两点间的距离公式与线段中点的坐标公式的运用．

【教学难点】

两点间的距离公式的理解．

【教学备品】

三角板．

【教学方法】

讨论合作法

【课时安排】

2课时．(90分钟)

【教学设计】

针对学生的情况，本人在教学中的引入尽量安排多个实例，多讲具体的东西，少说抽象的东西，以激发学生的学习兴趣

在图中搜索两点间所有路径的M文件

function possiablePaths = findPath(Graph, partialPath, destination, partialWeight) % findPath按深度优先搜索所有可能的从partialPath出发到destination的路径，这些路径中不包含环路

% Graph: 路网图，非无穷或0表示两节点之间直接连通，矩阵值就为路网权值 % partialPath: 出发的路径，如果partialPath就一个数，表示这个就是起始点 % destination: 目标节点

% partialWeight: partialPath的权值，当partialPath为一个数时，partialWeight为0 pathLength = length(partialPath);

lastNode = partialPath(pathLength); %得到最后一个节点

nextNodes = find(0

% 如果lastNode与目标节点相等，则说明partialPath就是从其出发到目标节点的路径，结果只有这一个，直接返回 possiablePaths = partialPath;

3.3.2 两点间的距离

一、教材分析

距离概念，在日常生活中经常遇到，学生在初中平面几何中已经学习了两点间的距离、点到直线的距离、两条平行线间的距离的概念,到高一立体几何中又学习了异面直线距离、点到平面的距离、两个平面间的距离等.其基础是两点间的距离，许多距离的计算都转化为两点间的距离.在平面直角坐标系中任意两点间的距离是解析几何重要的基本概念和公式.到复平面内又出现两点间距离，它为以后学习圆锥曲线、动点到定点的距离、动点到定直线的距离打下基础，为探求圆锥曲线方程打下基础.

解析几何是通过代数运算来研究几何图形的形状、大小和位置关系的，因此，在学习解析几何时应充分利用“数形”结合的数学思想和方法.

在此之前，学生已学习了直线的方程、两直线的交点坐标，学习本节的目的是让学生知道平面坐标系内任意两点距离的求法公式，以及用坐标法证明平面几何问题的知识，让学生体会到建立适当坐标系对于解决问题的重要性.

课堂教学应有利于学生的数学素质的形成与发展，即在课堂教学过程中，创设问题的情境，激发学生主动地发现问题、解决问题，充分调动学生学习的主动性、积极性；有效地渗透数学思想方法，发展学生个性思维品质，这是本节课的教学原则.根据这样

实验6无向图中求两点间的所有简单路径

背景

简单路径：如果一条路径上的顶点除了起点和终点可以相同外，其它顶点均不相同，则称此路径为一条简单路径。

问题描述

若用无向图表示高速公路网，其中顶点表示城市，边表示城市之间的高速公路。试设计一个找路程序，获取两个城市之间的所有简单路径。

基本要求

（1） 输入参数：结点总数，结点的城市编号（4位长的数字，例如电话区号，长沙

是0731），连接城市的高速公路（用高速公路连接的两个城市编号标记）。

（2） 输入 要求取所有简单路径的两个城市编号。

（3） 将所有路径（有城市编号组成）输出到用户指定的文件中。

实现提示

基于DFS的思想。

一、需求分析

城市分布不均，且无向，两个城市之间有路连接，根据特点，可以抽象成一个无向图，城市为各点，高速路为边。按照用户的输入建立一个邻接表，输出两个点的所有路径。

(1) 输入的形式和输入值的范围：本程序要求首先输入一个正整数值N，代表城市总数，然后依次输入城市的代号，可以用四位数字表示。因此，用整数来存储。

(2) 输出的形式：根据输入的数据，进行输入，若能成功，则将所有序列输出，若不能成功，则提示报错。

(3) 程序所能达到的功能：程序要求能够识别输入城市编号列表，高速公路，需要查找路径的两个城

DFS算法：遍历任意两点之间的所有路径并输出

代码大部分都是从数据结构书上来的，水平有限仅供参考！希望对课程设计要用到这个算法的同学有帮助

先看运行结果： 起点1，终点7

基本代码都是从数据结构书上抄来的，重点看红字。

全部源代码

//mian的实现

#include \#include \#include \#include \#include \#include %using namespace std;

void PrintPath(AList* path){ //打印路径 int L=path->Length(); int temp=-1; for(int i=0;isetPos(i); path->getValue(temp); cout

void DFS(Graph* G,int v,int end,AList* path){ G->setMark(v,VISITED); //标记为已访问，防止路径重复 path->append(v); //记录节点

if(v==end) //到达终点 //在这里对路径