复杂网络的任意m子节点间的网络最短距离的求解

本文内容来自本人的python期末作业，发布出来是希望能给一些解题的思路给需要的人

• 一、问题描述
• 二、解答的思路

`

所谓“网络”（networks），实际上就是节点（node）和连边（edge）的集合。如果节点对（i，j）与（j，i）对应为同一条边，那么该网络为无向网络（undirected networks），否则为有向网络（directed networks）。如果给每条边都赋予相应的权值，那么该网络就为加权网络（weighted networks），否则为无权网络（unweighted networks），如图2-1所示。

图2-1 网络类型示例

(a) 无权无向网络   (b) 加权网络   （c)无权有向网络

如果节点按照确定的规则连边，所得到的网络就称为“规则网络”（regular networks）。如果节点按照完全随机的方式连边，所得到的网络就称为“随机网络”（random networks）。如果节点按照某种（自）组织原则的方式连边，将演化成各种不同的网络，称为“复杂网络”（complex networks）。
常见的存图的方式有三种。

①邻接矩阵，即用二维数组实现，G[u][v]为边的权值，不加权的话把权重看成1即可。

②邻接表，在C/C++竞赛中一般用vector G[MAXN_V]来模拟邻接表结构，邻接表适用于疏密图，相比起邻接矩阵会节省空间。优点即学起来快，可读性高，可以方便配合C++里的STL。

③链式前向星，这也是我在用C/C++打算法竞赛中存图常用的数据结构了。我接下来在python的程序就要使用这个数据结构。

 经过研究探讨，发现这是一个斯坦纳树，一个组合优化问题。与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。也就是最小斯坦纳树中的节点可以借助不在网络中的节点当“踏板”从而可能可以得到更短的连通所需的路径。所以题目就是要解答出若干个斯坦纳树。
首先得知道答案的子图一定是树，因为如果答案存在环，则删去环上任意一条边，总的连通代价会变小。接着设 dp[i][s] 表示以 i 为根的一棵树，包含题目中所要求的集合 S 中所有点的最小代价。具体的状态转移和算法流程图见3程序流程及系统设计.
 纵观m=2、3、4、5、6的情况，随着m的增大，最短网络距离的长度普遍都会增大，也就是连通m个节点的代价变大了，但是每次的运行时间还是非常快的，几乎都不到1s就能跑出结果，当然是m个网络子节点要选好的前提。原因应该得益于链式前向星的存图方式、堆的优化后的dijkstra和最小斯坦纳树的算法设计。

解答的代码可以参考我之前写的这篇P6192 【模板】最小斯坦纳树——最小斯坦纳树。
不过是C++版本的，想着把python版的代码放上来有点不完整，因为它需要配合csv格式的输入文件才能运行。输入的复杂网络数据是以我们校园为背景的。

我直接把文件上传到CSDN，需要的自行下载吧，文件如下↓
附件