如何计算多向图中几个节点不相连的平均最短路径长度？
我想在我的多方向图中计算平均\u最短路径\u长度，但有一个节点未与其他节点连接
例如，我有一个具有节点和边的网络，如下所示：
lst_nodes=[2782, 27118, 28931, 28936, 43162, 28770, 48325, 33783]
lst_edge = [(28931, 28936L), (28931, 27118L), (28931, 27118L), (28931, 33783L), (48325, 28936L), (28936, 43162L),
(28936, 48325L), (27118, 28936L), (27118, 28936L), (27118, 48325L), (43162, 48325L), (2782, 28931L),
(2782, 48325L), (2782, 48325L), (2782, 27118L), (2782, 33783L)]
MDG = nx.MultiDiGraph()
MDG.add_nodes_from(lst_nodes)
MDG.add_edges_from(lst_edge)
print 'avg shortest path length:', nx.average_shortest_path_length(MDG)
它将以如下异常结束
networkx.exception.NetworkXError：图形未连接。
但是根据NetworkX上的注释
对于断开连接的图形，可以计算每个组件的平均最短路径长度：
它应该与组件一起工作，所以我之前尝试过代码
for g in nx.connected_component_subgraphs(MDG):
print nx.average_shortest_path_length(g)
但最终出现了一个异常，如networkx。例外NetworkXNotImplemented：未针对定向类型实施，但是如果我从网络中删除单个节点，我可以计算网络的平均最短路径长度，因此我想知道如何计算多个节点未连接的多定向图中的平均最短路径长度？
共有1个答案
事实上，我认为nx.shortest_path_length是最合理的解决方案：
import statistics
from itertools import chain
# This includes the isolated node!
path_lengths = (x.values() for x in nx.shortest_path_length(MDG).values())
statistics.mean(chain.from_iterable(path_lengths))
# 1
-
我有一个一般性的问题，关于如何在边没有权的无向图中找到最短路径和最长路径。 我们需要使用DFS算法来寻找图中的最长路径，而我们需要使用BFS算法来寻找图中的最短路径，这是一个正确的结论吗？
-
我确实有一个图(~250个节点）。要连接到一个节点，我必须用points->加权图购买它。有些节点总是被占用（“声明的节点”），我可以从这些节点开始连接到其他节点。此外，我的点数有限。所有节点都可以连接在一起。 有什么方法可以得到一个图，其中所有的节点都必须连接在一起，点最少？如果可能的话，以给定的最大点数。 第二）有没有一种方法可以使它不需要一个完全连通的图？例如：一个“必须有节点”的节点直接连
-
你知道如何克服这个问题吗？
-
我有一个由未加权边构建的图（a），我想计算主图（a）中最大连通图（giantC）的平均最短路径长度。但是，到目前为止，该脚本已经运行了3个多小时（在Colab和本地进行了尝试），对于和都没有输出任何结果。 我使用的是， 这是我的剧本 有没有办法让它更快？或者是计算giantC图的直径和最短路径长度的替代方法？
-
我试图弄清楚，如何计算具有加权顶点的图的最短路径。经典算法，如Dijkstra和Floyd-WarMarshall，通常使用加权边，我看不到如何将它们应用于我的情况（加权顶点）： 我的一个想法是将图形转换为带有加权边的更经典的视图。这是我收到的： 这里我们有单向和双向加权边，但我仍然不确定哪种算法可以处理这一点，以找到最短路径。
-
如何计算路径的平均路径长度是一个，或两个在networkx？例如，在下面的图表中，平均路径长度等于一是6，二是2。