Макс из списка всех кратчайших путей между двумя узлами

Question

У меня есть неориентированный граф

Я хотел бы, чтобы вычислить максимальные из списка всех кратчайшей длиной между двумя узлами в сети, какие-либо идеи, как я может это сделать?

Answer 1

Я думаю, что вам нужен диаметр графа, который является максимальным кратчайшим путем для всех пар. https://networkx.github.io/documentation/latest/reference/generated/networkx.algorithms.distance_measures.diameter.html

Answer 2

Если вы хотите, чтобы рассмотреть некоторое подмножество вершин для источника и цели, вы можете сделать что-то вроде:

# Change these to fit your needs 
sources = G.nodes()  # For example, sources = [0,1,4] 
targets = G.nodes() 

max_shortest_path = None 
for (s,t) in itertools.product(sources, targets): 
    if s == t: continue # Ignore 
    shortest_paths = list(nx.all_shortest_paths(G, s, t)) 
    path_len = len(shortest_paths[0]) 
    if max_shortest_path is None or path_len > len(max_shortest_path[0]): 
     max_shortest_path = list(shortest_paths) # Copy shortest_paths list 
    elif path_len == len(max_shortest_path[0]): 
     max_shortest_path.extend(shortest_paths) 

После этого max_shortest_path список. Все элементы max_shortest_path являются списками одинаковой длины.

len(max_shortest_path[0]) доставит вас длина максимальной длины на графике.

Элементы max_shortest_path являются дорожками этой длины.