求两点之间最短的距离矩阵

题目某公司在六个城市C 1,C 2,C 3,C 4,C 5,C 6都有分公司，公司成员经常往来于它们之间，已知从Ci 到C j 的直达航班票价由下述矩阵的第i 行，第j 列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。

.摘要改革开发以来，我国的经济发展迅速，人民生活水平逐渐提高，2010年，我国GDP 超越日本，排名世界第二。

我国经济的发展，使人们对交通运输提出越来越多的需求， 而民航作为航空运输工具，在交通工具中起到十分重要的作用，新型飞机(民用)快速、续航能力强、安全、便捷的特点受到越来越多的人青睐。

如果从交错复杂的飞机线路中找到最廉价的线路，不仅减少了中途时间，而且大大节省了开支费用，为企业和个人带来可观的经济效益。

本文从航班网络的实际特点出发，对航班线路网和票价进行分析，将最佳路径搜索问题转化为图论中的最短路径的问题，通过对最短路径算法的分析，实现了Floyd 算法求航班网络中的最短路径，将之建立模型，并描述了用matlab 程序进行求解的过程。

关键词：最短路 matlab Floyd 算法《*050402510500152025150102040201001025252010055102525550∞∞∞∞∞∞⎡⎣⎢⎢⎢⎢⎢⎢⎢⎤⎦⎥⎥⎥⎥⎥⎥⎥问题提出某公司在六个城市C 1,C 2,C 3,C 4,C 5,C 6都有分公司，公司成员经常往来于它们之间，已知从Ci 到C j 的直达航班票价由下述矩阵的第i 行，第j 列元素给出（表示无直达航班），该公司想算出一张任意两个城市之间的最廉价路线航费表。

问题分析若网络中的每条边都有一个数值(长度、成本、时间等)，则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短路问题，我们通常归属为三类：单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。

最短路问题(short-path problem)若网络中的每条边都有一个权值值(长度、成本、时间等)，则找出两节点(通常是源节点与结束点)之间总权和最小的路径就是最短路问题。

最短路问题是网络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。

最短路问题，我们通常归属为三类：单源最短路径问题（确定起点或确定终点的最短路径问题）、确定起点终点的最短路径问题（两节点之间的最短路径）1、Dijkstra算法：用邻接矩阵a表示带权有向图，d为从v0出发到图上其余各顶点可能达到的最短路径长度值，以v0为起点做一次dijkstra，便可以求出从结点v0到其他结点的最短路径长度代码：procedure dijkstra（v0：longint）；//v0为起点做一次dijkstrabegin//a数组是邻接矩阵，a[i,j]表示i到j的距离，无边就为maxlongintfor i:=1 to n do d[i]:=a[v0,i];//初始化d数组（用于记录从v0到结点i的最短路径）， fillchar(visit,sizeof(visit),false);//每个结点都未被连接到路径里visit[v0]:=true;//已经连接v0结点for i:=1 to n-1 do//剩下n-1个节点未加入路径里；beginmin:=maxlongint;//初始化minfor j:=1 to n do//找从v0开始到目前为止，哪个结点作为下一个连接起点（*可优化） if (not visit[j]) and (min>d[j]) then//结点k要未被连接进去且最小begin min:=d[j];k:=j;end;visit[k]:=true;//连接进去for j:=1 to n do//刷新数组d，通过k来更新到达未连接进去的节点最小值，if (not visit[j]) and (d[j]>d[k]+a[k,j]) then d[j]:=a[k,j]+d[k];end;writeln(d[n]);//结点v0到结点n的最短路。

最短路径的算法最短路径的算法小河边有两个村庄A，B，要在河边建一自来水厂向A村与B村供水，若要使厂部到A，B村的距离相等，则应选择在哪建厂?要回答出这个问题，我们就要了解一下最短路径的相关知识。

以下是店铺与大家分享最短路径的知识。

最短路径最短路径，是指用于计算一个节点到所有节点的最短的线路。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

最短路径问题是图论研究中的一个经典算法问题，旨在图(由结点和路径组成的)中两结点之间的最短路径。

最短路径问题最短路径问题是图论研究中的一个经典算法问题，旨在寻找图(由结点和路径组成的)中两结点之间的最短路径。

算法具体的形式包括：确定起点的最短路径问题- 即已知起始结点，求最短路径的问题。

适合使用Dijkstra算法。

确定终点的最短路径问题- 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。

在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。

确定起点终点的最短路径问题- 即已知起点和终点，求两结点之间的最短路径。

全局最短路径问题- 求图中所有的最短路径。

适合使用Floyd-Warshall算法。

Dijkstra算法1.定义概览Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

Dijkstra算法是很有代表性的最短路径算法，在很多课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。

注意该算法要求图中不存在负权边。

问题描述：在无向图 G=(V,E) 中，假设每条边 E[i] 的长度为 w[i]，找到由顶点 V0 到其余各点的最短路径。

(单源最短路径)2.算法描述1)算法思想：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示，初始时S中只有一个源点，以后每求得一条最短路径 , 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了)，第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。

v 弗洛伊德算法弗洛伊德算法（Floyd’s algorithm），又称为插点法，是一种通过动态规划求解最短路径问题的算法。

该算法在图论中有着广泛的应用，能够快速求解出两点之间的最短路径。

本文将为大家介绍弗洛伊德算法的原理以及实际应用。

1. 算法原理弗洛伊德算法的核心思想是利用中间点来更新起点到终点的距离。

假设图中任意两点之间的距离都为$d[i][j]$，则我们假设存在一个中间点$k$，可以将起点$i$和终点$j$之间的最短路径分成两部分，即起点到中间点的路径$d[i][k]$和中间点到终点的路径$d[k][j]$。

所以我们可以得到如下的状态转移方程：$$d[i][j]=\min(d[i][j],d[i][k]+d[k][j])$$通过不断地更新所有点之间的最短路径，我们最终可以得到所有节点之间的最短路径。

2. 算法实现弗洛伊德算法的实现中，最重要的一步就是更新状态转移方程。

具体来说，我们需要使用三层循环嵌套遍历所有点，将当前节点到所有其他节点的最短距离更新一遍即可。

下面就是使用 Python 语言实现弗洛伊德算法的代码片段：```pythonn = len(graph)for k in range(n):for i in range(n):for j in range(n):graph[i][j] = min(graph[i][j], graph[i][k] +graph[k][j])```在这段代码中，$graph$是一个$n \times n$的矩阵，表示所有节点之间的距离。

其中$n$是节点的数量。

3. 算法应用弗洛伊德算法的主要应用是求解带权图中各个节点之间的最短路径。

在实际生活中，我们可以将节点看作是城市，将距离看作是两个城市之间的道路距离。

这样，就可以使用弗洛伊德算法来计算任意两座城市之间的最短路程，帮助人们规划出更加便捷的旅行路线。

另外，在计算机网络中，弗洛伊德算法也被广泛应用于路由协议的设计中。

最短路径在一个无权的图中，若从一个顶点到另一个顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。

由于从一个顶点到另一个顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，把路径长度最短（即经过的边数最少）的那条路径叫作最短路径或者最短距离。

对于带权的图，考虑路径上各边的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或带权路径长度。

从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或最短距离。

最短路径算法Dijkstra算法：该算法是用于求解单源点最短路径的实用算法。

Dijkstra算法的基本思想如下：设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S其中，V为网中所有顶点集合。

按最短路径长度递增的顺序逐个用V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。

Dijkstra算法的具体步骤；（1）设源点为V1，则S中只包含顶点V1，令W=V-S，则W中包含除V1外图中所有顶点。

V1对应的距离值为0，即D[1]=0。

W中顶点对应的距离值是这样规定的：若图中有弧 <v1,vk>，则Vj顶点的距离为此弧权值，否则为一个无穷大的数；（2）从W中选择一个其距离值最小的顶点 vk，并加入到S中；（3）每往S中加入一个顶点vk后，就要对W中各个顶点的距离值进行一次修改。

若加进vk做中间顶点，使<v1,vk> + <vk+vj>的值小于<v1,vj> 值，则用<v1,vk> + <vk+vj>代替原来vj 的距离值；（4）重复步骤2和3，即在修改过的W中的选距离值最小的顶点加入到S 中，并修改W中的各个顶点的距离值，如此进行下去，知道S中包含图中所有顶点为之，即S=V。