欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-13 12:28:17
...

第一部分:

    基于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

相关标签: graph networkx