Python: Networkx Dijkstra算法的问题

Question

我的目标是做和这里上说的一模一样的事情。

我有一个矩阵（DataFrame 或者 df），看起来像这样：

community A   B   C   D
A         0   3   4   1
B         3   0   2   0
C         4   2   0   1
D         1   0   1   0 

这个df是对称的，每个权重代表了不同社区之间连接的强度。正如链接中所解释的，我想生成一个矩阵，显示所有节点（或社区）之间的最短距离。我首先对上面的矩阵进行反转，并设置G图网络：

G = nx.Graph()
commu = list(df.index)
for i in range(0,len(commu)):
    for j in range(0,len(commu)):
            if i == j:
                pass
            else:
                G.add_edge(str(i),str(j),weight=df.ix[df.index[i], df.columns[j]])

这给了我下面这个网络图： 边的不同颜色代表不同的权重。（我在我的图中把字母换成了数字）

到目前为止，一切都很好。现在，我想找出所有节点之间的最短距离。我在考虑使用nx.dijkstra_shortest_path_length(G,source,target)，然后对所有节点进行循环，作为source和target，生成一个像上面链接那样的矩阵，矩阵中的每个单元格都包含所有节点之间的最短路径值，但不知为什么nx.dijkstra_shortest_path_length(G,source,target)对我不起作用。如果我用nx.dijkstra_shortest_path_length(G,A,B)或者任何节点组合，我总是得到0的值。为什么会这样？有没有什么有效的方法可以使用Networkx和nx.dijkstra算法来生成像链接中那样的矩阵？

Answer 1

(这不是答案，只是一个长长的评论)。 如果

In [65]: df.values
Out[65]: 
array([[0, 3, 4, 1],
       [3, 0, 2, 0],
       [4, 2, 0, 1],
       [1, 0, 1, 0]], dtype=int64)

那么可以用

G = nx.Graph()
commu = list(df.index)
for i in range(0,len(commu)):
    for j in range(0,len(commu)):
            if i == j:
                pass
            else:
                G.add_edge(str(i),str(j),weight=df.ix[df.index[i], df.columns[j]])

来构建G，方法是

In [66]: G = nx.from_numpy_matrix(df.values)

In [67]: G.edges(data=True)
Out[67]: 
[(0, 1, {'weight': 3}),
 (0, 2, {'weight': 4}),
 (0, 3, {'weight': 1}),
 (1, 2, {'weight': 2}),
 (2, 3, {'weight': 1})]

如果你想把节点标记为ABCD而不是0123，可以这样做：

In [68]: G = nx.relabel_nodes(G, dict(zip(range(4), 'ABCD')))

In [69]: G.edges(data=True)
Out[69]: 
[('A', 'C', {'weight': 4}),
 ('A', 'B', {'weight': 3}),
 ('A', 'D', {'weight': 1}),
 ('C', 'B', {'weight': 2}),
 ('C', 'D', {'weight': 1})]

Answer 2

你可以直接使用 networkx.shortest_path(G) 这个函数，并加上一个叫做 weight 的参数，设置为 'weight'。比如：

In [1]: import networkx as nx

In [2]: G = nx.Graph()

In [3]: G.add_edge(1,2,weight=7)

In [4]: G.add_edge(1,4,weight=3)

In [5]: G.add_edge(2,3,weight=1)

In [6]: G.add_edge(3,4,weight=100)

In [7]: nx.adjacency_matrix(G).todense()
Out[7]: 
matrix([[  0,   7,   0,   3],
        [  7,   0,   1,   0],
        [  0,   1,   0, 100],
        [  3,   0, 100,   0]])

In [8]: nx.shortest_path_length(G)
Out[8]: 
{1: {1: 0, 2: 1, 3: 2, 4: 1},
 2: {1: 1, 2: 0, 3: 1, 4: 2},
 3: {1: 2, 2: 1, 3: 0, 4: 1},
 4: {1: 1, 2: 2, 3: 1, 4: 0}}

In [9]: nx.shortest_path_length(G,weight='weight')
Out[9]: 
{1: {1: 0, 2: 7, 3: 8, 4: 3},
 2: {1: 7, 2: 0, 3: 1, 4: 10},
 3: {1: 8, 2: 1, 3: 0, 4: 11},
 4: {1: 3, 2: 10, 3: 11, 4: 0}}

In [10]: nx.utils.dict_to_numpy_array(nx.shortest_path_length(G,weight='weight'))
Out[10]: 
array([[  0.,   7.,   8.,   3.],
       [  7.,   0.,   1.,  10.],
       [  8.,   1.,   0.,  11.],
       [  3.,  10.,  11.,   0.]])