浅谈如何使用python复杂网络选择任意子节点计算出该任意子节点之间的最短连通距离，只用于记录，不是教程不是教程不是教程！！！
首先要明白，复杂网络任意子节点的网络最短距离是最小生成树的一种，但和传统意义上的prim或kruskal算法求解最小生成树的方法略微不同。
传统意义上的prim或kruskal算法，选择的是遍历该网络图/树形图中的所有节点，在不生成环形的情况下选择每两个节点集之间的最短距离（权值），生成最小生成树。要了解prim算法或kruskal算法的原理流程，详情请见：
最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示_哔哩哔哩_bilibili
而在本道开放性的实验题型中，并没有类似于prim或者kruskal之类的最小生成树通解，因为本题需要的是 复杂网络任意子节点的网络最短距离，并不是遍历整个网络图的所有节点输出最小生成树。复杂网络中任意子节点的网络最短距离，实际上是求解该几个子节点组成的子网络的最小生成树。
所以现在问题变成了：
如何求解这几个子节点组成的子网络的最小生成树？
本次实验以任意子节点数量n = 5来举例。
要了解这个问题，首先要把网络拓扑图/树形图转化为邻接矩阵，本次以一个六节点的带权无向图为例。
如图所示，右图为该带权无向图，左边为该图的邻接矩阵，若两点可达，则设m为邻接矩阵，i为行号，j为列号，m[i][j]为两点之间的权值；若两点不可达，则m[i][j]为0。
通过这个邻接矩阵我们可以得出两点之间的权值与连线情况，而任意n=5个子节点组成的子网络实际上就是该邻接矩阵中的对应节点组成的邻接矩阵。如n=1，3，4，5，6，实际上就是把行数=2（2，0，0，0，4，6），列数=2（2，0，0，0，4，6）的元组从该邻接矩阵中剔除，留下由节点1，3，4，5，6组成的邻接矩阵，同理可以延伸到更大的网络矩阵，比如从34x34的邻接矩阵中抽出由5个节点组成的邻接矩阵，也是类似的情况。
现在让我们回到这个问题： 如何求解这几个子节点组成的子网络的最小生成树？
让我来简单地陈述一下算法流程：
- 得到带权无向图的邻接矩阵将对角线全设为0（自身到自身的距离），两点不可达时设置为Infinity，这里的无穷大也可以是一个远大于邻接矩阵权值的数，如99，999，1024等，根据你的邻接矩阵权值选择。该矩阵为一跳矩阵，意为第一次变化的矩阵。通过dijkstra或floyd算法，算出该带权无向图中每两个子节点的最短距离，得出一个最短距离矩阵，接下来根据改良过后的prim算法一步一步得出这几个节点的最小生成树，在此之前可以先了解prim算法的算法流程。算出最短距离矩阵中每一行的总权值，以此类推，对比每一行的权值，选出一个权值最小的行，实际上此行就可以当做第一个最短距离的子节点。因为这个总权值实际上就是该节点到每一个节点的距离。从第一个节点出发，选择该行的最小值，拿到这个最小值的索引，在与该索引对应的下一行中去除本身与遍历过的节点，在这两行之间选择最小值。循环步骤5，得出最短权值。
以上为该算法的简单流程，可能这样看起来比较抽象，接下来结合floyd算法与改良后的prim算法流程图来讲解该算法运行的流程。
FOLYD算法
Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。
——————百度百科
简单的来说，算法的主要思想是动态规划(dp)，而求最短路径需要不断松弛（熟悉spfa算法的可能熟悉松弛）。
源地址为：多源最短路径算法—Floyd算法 - bigsai - 博客园
而算法的具体思想为：
- 邻接矩阵dist储存路径，同时最终状态代表点点的最短路径。如果没有直接相连的两点那么默认为一个很大的值(不要溢出)！而自己的长度为0.从第1个到第n个点依次加入图中。每个点加入进行试探是否有路径长度被更改。而上述试探具体方法为遍历图中每一个点(i,j双重循环)，判断每一个点对距离是否因为加入的点而发生最小距离变化。如果发生改变，那么两点(i,j)距离就更改。重复上述直到最后插点试探完成。
其中第三步的状态转移方程为:
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
其中dp[x][y]的意思可以理解为x到y的最短路径。所以dp[i][k]的意思可以理解为i到k的最短路径dp[k][j]的意思可以理解为k到j的最短路径.
从上面的案例出发：
默认的最短长度初始为邻接矩阵初始状态
加入第一个节点1,大家可以发现，由于1的加入，使得本来不连通的2，3点对和2，4点对变得联通，并且加入1后距离为当前最小。(可以很直观加入5之后2，4，更短但是还没加入)。为了更好的描述其实此时的直接联通点多了两条。(2,3)和(2,4).我们在dp中不管这个结果是通过前面那些步骤来的，但是在这个状态，这两点的最短距离就算它！
同时你可以发现加入1其中也使得3,1,4这样联通，但是 3,1,4联通的话距离为9远远大于本来的(3,4)为2，所以不进行更新。
咱们继续加入第二个节点。在加入的初始态为：
进行遍历插入看看是否更新节点
实际上这个时候图中的连线就比较多了。当然这些连线都是代表当前的最短路径。 这也和我们的需求贴合，我们最终要的是所有节点的最短路径。每个节点最终都应该有6条指向不同节点的边！ 表示邻接矩阵的最终结果。
至于算法的模拟两部核心已经告诉大家了，大家可以自行模拟剩下的。
事实上，用代码实现该算法极其简单（python）
def floyd(n): # floyd算法
for k in range(n):
for i in range(n):
for j in range(n):
chosen_[i][j] = min(chosen_[i][j], chosen_[i][k] + chosen_[k][j])
return chosen_
而上述案例生成的最短路径矩阵为：
适用于本题的Prim算法
普里姆算法（Prim算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小
————百度百科
在本题中，实际上也是基于prim算法的变式，同样是选择两个节点集合中最小权值的边，构成最小生成树。为了方便称呼，以下的“prim算法”均指的是本题改良过后的prim算法，若要了解原版算法请戳楼上b站链接。
我们把上面的prim算法流程拿下来：
通过dijkstra或floyd算法，算出该带权无向图中每两个子节点的最短距离，得出一个最短距离矩阵，接下来根据改良过后的prim算法一步一步得出这几个节点的最小生成树，在此之前可以先了解prim算法的算法流程。算出最短距离矩阵中每一行的总权值，以此类推，对比每一行的权值，选出一个权值最小的行，实际上此行就可以当做第一个最短距离的子节点。因为这个总权值实际上就是该节点到每一个节点的距离。从第一个节点出发，选择该行的最小值，拿到这个最小值的索引，在与该索引对应的下一行中去除本身与遍历过的节点，在这两行之间选择最小值。循环上步，得出最短权值。
现在我们通过图来解释该算法的运作流程：
首先看到上述带权无向图中floyd算法得出的最短路径矩阵
第一步：
通过dijkstra或floyd算法，算出该带权无向图中每两个子节点的最短距离，得出一个最短距离矩阵，接下来根据改良过后的prim算法一步一步得出这几个节点的最小生成树。
假设我们现在要选五个点，n=1，3，4，5，6；则从这个最短路径矩阵中抽出来的矩阵如下：
第二步：
算出最短距离矩阵中每一行的总权值，以此类推，对比每一行的权值，选出一个权值最小的行，实际上此行就可以当做第一个最短距离的子节点。因为这个总权值实际上就是该节点到每一个节点的距离。
如下图，在这五个节点组成的矩阵中，1，3，4，5，6行的总和分别为22，13，11，14，20。
那就选择的总和最小的4作为第一个节点。
我们需要创建一个数据结构——遍历矩阵，用于存放选择过的行。
那么遍历矩阵就为：4（5，2，0，1，3）
第三步：
从第一个节点出发，选择该行的最小值，拿到这个最小值的索引，在与该索引对应的下一行中去除本身与遍历过的节点，在这两行之间选择最小值。
首先我们在选择最小值得时候，一定要注意把自己本身以及访问过的节点给去除，现在从第一个节点出发：
去除本身0，该行选择的最小值是1，所以1索引为5，下一步要把第五行加入遍历矩阵中，并且去除本身与遍历过的节点。
那么此时遍历矩阵就为：4（5，2，0，1，3）
5（6，3，1，0，4）
第四步：
从上一步的遍历矩阵中找到最小值，注意是在遍历矩阵中找，去除本身与遍历过的节点后（本身就是0，遍历过的节点就是红色的），遍历矩阵中最小值为2，这个2就是两个节点集中的最短边，索引为3，所以下一步要把第三行加入遍历矩阵。
那么此时遍历矩阵就为： 4（5，2，0，1，3）
5（6，3，1，0，4）
3（3，0，2，3，5）
第五步：
重复上述步骤，把最小值3的索引1加入遍历矩阵： 4（5，2，0，1，3）
5（6，3，1，0，4）
3（3，0，2，3，5）
1（0，3，5，6，8）
第六步：
然后把第一行加进来，找最小权值，若有相同的则随便选一个。
至此，由于节点数为n=5，则最小生成树的边为n-1=4，目前已经选择了最短路径的四个节点
节点分别为（按选择顺序排序）：4，5，3，1，6(前四个是选出来的，最后一个不用选直接排)
权值分别为（按选择顺序排序）：1，2，3，3
所以1，3，4，5，6组成的子网络的最小生成树节点为4，5，3，1，6；权值分别为1，2，3，3；权值总和为9，路径如图
最后附上流程图：
