在有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
上一篇: js实现在不重复的数组m中找到N位不重复的数的所有组合
下一篇: 求1到10阶乘之和