军事通讯网络的最短路径研究分析

戴涵竹　詹清钦　季堂煜

摘要：应军事斗争战备要求，本文需要设计构建包含139个大中型城市作为节点的有线通信网络，在每个城市内设置一架专用网络连接设备，在确保全连通的情况下球的最短的通信线路的总长度。首先，本文使用Kruskal算法并对计算出的所有两点间距离进行排序，通过使用递归调用函数，遍历循环所有的节点，通过不断比较，在生成完139个数据的连线后，结束遍历获得最短路径，并通过调用百度地图API来模拟最小生成树进行显示，增加了可读性。

关键词：Kruskal算法 最短路径 路线图

前言

在信息化高度发展的当代，信息化战争是现代化战争的新模式，因而我国需要加强信息化战队建设。由此来看构建兼顾连通性和经济性的通信网络变得极其重要。当面对部分网络遭到破坏时，能够及时准确做出最优修复方案来解决问题也是我国需要重点投入研究的方向。

1模型建立与求解

1.1最小生成树的路线优化模型

本部分建立了城市间通信网络互通最短路径选择模型，主要研究经过所有城市基站且路径总和最短的数学模型与算法。使用最小生成树优化算法找出连接139座城市的最短總路线，在满足基本连通性能的基础上尽可能降低经济成本。

1.2不同目标点经纬度的无向赋权图

引用图论相关知识，可以将题目所给每座城市的经纬度条件绘制成无向赋权图。G（V，E，w），G中每个顶点为每个城市基站连接点（即为城市的中心经纬度点），V表示图中顶点顶点总数为E个，W表示图的权值，如w：表示v→V.的权值（不分方向，（i，j）∈E）。以经度为X轴纬度为Y轴建立二维坐标轴，将顶点放置于二维坐标图中，每个顶点可表示为v，（X，，Y，）。

1.3计算权值

顶点v，均可与任意其它节点形成互通连线，且基于假设，城市间的连接方式均采用最短距离连接。任意两座城市间的通信连接G→G可表示为：

1.4确定最短路径

本题使用最小生成树Kruskal优化算法，将所有权值进行从小到大的排序，从最小权值开始取，若取此权值支路作为最小路径则支路两端的Ⅵ，vj视为连通;将下一个最小权值作为目标支路，若目标支路两端节点均已连通且此支路的加人会使连通集合形成闭合回路则此支路不取为最短总路径的支路（不包括在最短路径中）;直至取到（139-1=） 138条支路，与此同时所有节点均已连通，则此138条支路构成的通路为最短路径。

Step2：利用经纬度数据计算节点间权值;

Step3：编写程序，生成最短路径;

Step4：将生成路径呈现于百度地图API上;

Step5：根据百度地图的显示，我们将某些能够更加优化的线路进行再次的探讨和优化。然后将优化完的数据再次通过百度地图进行显示。

法二，最小生成树的Prim 算法

Stepl：建立无向赋权图;

Step2：利用经纬度计算节点权值;

Step3：任意设定一个节点Vi作为起始点，取与之相连接的最小权值连线计人最短路径，此连线两端的端点计为连通点，将所有相互连通的节点（连通点）作为一个新的集合，再取与新集合相外接（除集合内节点以外与其他节点的连线）的最短连线计人最短路径，端点视为连通点，所有连通端点再次组成新的集合，依次推进，直至所有点连通找出138条连线组成最短路径按照以上Prim算法思路编写程序，生成最短路径

Step4：将生成路径呈现于百度地图API上。

方案选择

以上两个方案均可实现最小生成树的构建，由于本题已给出每个城市的具体经纬度数据，能构建通信网络连接图，并且能够计算出每一权值大小。因此进行大小排序比较能够更直观有效得到答案。本组选择了法一进行求解。

2模型分析

优点：

（1）最短路径寻找算法使用得当，使用Kruskal算法优化了路径求解。

（2）使用百度地图API方式呈现城市节点间的连线易于观察且美观。

缺点：

关于本题的讨论，本文仅仅将路径最短作为唯一约束条件，未考虑可行性和构建成本问题。例如：大连和烟台进行跨海连接。

参考文献

[1]李琳，刘雅奇.通信网节点重要性的多指标评价方法[J].海军工程大学学报，2010，22（5）：69-73.

[2]司守奎，孙兆亮.数学建模算法与应用，北京：国防工业出版社，2017.