Networkx 그래프의 가장자리를 곱하는 알고리즘

Question

내 문제는 Networkx 라이브러리로 구현 된 그래프에서 노드에서 다른 노드 (또는 같은 노드)까지 가장 긴 경로를 찾는 것입니다.

가장자리의 추를 추가하고 싶지는 않지만 곱해서 가장 큰 결과를 얻으 려합니다. 분명히 각 노드에 의해 한 번만 전달되거나 전혀 전달되지 않습니다. 내가 노드 4 노드 1에서 가고 싶은 경우

예를 들어, 최상의 결과는 다음과 같습니다 2 × 14 X 34 X 58

Graph example

여러분의 도움에 감사드립니다!

Answer 1

이 작동 할 수 있습니다

import networkx as nx 

G = nx.Graph() 

# create the graph 
G.add_edge(1, 2, weight=2) 
G.add_edge(1, 4, weight=5) 
G.add_edge(2, 3, weight=14) 
G.add_edge(2, 4, weight=5) 
G.add_edge(2, 5, weight=4) 
G.add_edge(3, 5, weight=34) 
G.add_edge(4, 5, weight=58) 

start = 1 # start node 
end = 4 # end node 

all_paths = [path for path in nx.all_simple_paths(G, start, end)] 

# initialize result 
largest_path = None 
largest_path_weight = None 

# iterate through all paths to find the largest 
for p in all_paths:          # keep track of each path 
    for _ in range(len(p)):        # for each node in this path 
     pairs = zip(p, p[1:])        # get sequence of nodes 
     product = 1          # reset product for this paths calculation 
     for pair in pairs:        # for each pair of nodes in this path 
      an_edge = G.get_edge_data(pair[0], pair[1]) # get this edge's data 
      product *= an_edge['weight']     # multiply all weights 
    if product > largest_path_weight:      # check if this path's product is greater 
     largest_path = p         # if True, set largest to this path 
     largest_path_weight = product      # save the weight of this path 

# display result 
print 'largest path:', largest_path 
print 'weight:', largest_path_weight 

을이 예를 들어 :

largest path: [1, 2, 3, 5, 4] 
weight: 55216