在有m个顶点的完全图中找到路径长度为n的最短路径，从任意顶点出发到任意顶点结束

第一部分：

    基于networkx再开发, networkx是操作图或网络的一个python包，可以通过它的一些实例来学习一下：https://networkx.github.io/documentation/stable/tutorial.html。

     本文利用图解决固定长度的最短路径问题：由m个节点构成一个无向完全图（每个节点到其他节点都有一条边），找到路径长度为n的最短路径，其中顶点以阿拉伯数字1,2,3,...表示。

    例如，当m=3,n=2时，算法将通过m个顶点的权重矩阵[(0,1,2),(1,0,1),(2,1,0)]计算得到从每个顶点出发，到达每个顶点的权重最小值且路径长度为2：本小例的输出矩阵为[(0,3,2),(3,0,3),(2,3,0)] 。

    带有yeild的函数就拥有了迭代能力，注意区分 fab 和 fab(5)，fab 是一个 generator function，而 fab(5) 是调用 fab 返回的一个 generator，好比类的定义和类的实例的区别：fab不可以迭代，fab(5)可以迭代。

     return和pass的区别：if(条件) return  #如果条件满足，则跳出if 语句；pass则表示继续执行满足if 条件的语句。

     本文通过三个步骤实现，算法的安排如下：

     首先给出3个步骤的分开实现 1）生成任意完全图； 2）将完全图的节点按照任意的路径长度全排列； 3）计算全排列中开始节点到终止节点相同的所有排列的最小权重

      最后将三个步骤的算法的功能连接起来使用，至此，算法结束

1）生成任意的完全图

import networkx as nx

G = nx.Graph()
def iuputData():
    graphNode=[]
    weight=[]
    m = input('Input the size of graph:')
    for i in range(0,m):
        graphNode.append(i)
    # list to string
    toSting="".join(str(x) for x in graphNode)
    G.add_nodes_from(toSting)
    # add the weight for input graph
    # get the weight
    for i in range(0, m):
        for j in range(0, m):
            if (j >= i):
                w=j-i
                weightEdge=str(i)+" "+str(j)+" "+str(w)
                weight.append(weightEdge)
    # deal data to regular style
    finaldata=[]
    for f in range(1,len(weight)):
        wei= weight[f].replace(" ","")
        findata2=[]
        findata=tuple(wei)
        for l in range(0,3):
            findata2.append(int(findata[l]))
        findata3=tuple(findata2)
        finaldata.append(findata3)

    # add the weight in graph
    G.add_weighted_edges_from(finaldata)
    return G

# rebuild the input graph
IG=nx.Graph(iuputData())

2）将完全图中的节点根据给定的路径长度全排列

# list all the permutations for our complete graph
allPer=[]
r = input("input the path length:")
Inodes = input("Input the nodes and length shpould be longer than r's value, as 123 or abc:")
Inodes = str(Inodes)
pool = tuple(Inodes)

n = len(pool)
r = n if r is None else r
if r <= n:
    indices = range(n)
    cycles = range(n, n - r, -1)
    print(tuple(pool[i] for i in indices[:r]))
    ilterNum = 1
    for n1 in range(1,n+1):
        ilterNum = ilterNum*n1
    while ilterNum>0:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i + 1:] + indices[i:i + 1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                allPer.append(tuple(pool[i] for i in indices[:r]))
                print(tuple(pool[i] for i in indices[:r]))
                break
        ilterNum -=1

3）计算开始节点与终止节点相同时的最小权重和

    在该小节中，首先根据首尾节点都相同这一条件将满足条件的路径都拿到，然后得到权重增加的最小值。

该步骤的具体实现将在下一篇博客中展示

：https://blog.csdn.net/dahuayaoer/article/details/81207154