在 networkx 库中使用 dijkstra_path 函数

Question

我正在使用 networkx 库使用 dijkstra 算法找到两个节点之间的最短路径，如下所示

import networkx as nx

A = [[0, 100, 0, 0 , 40, 0],
     [100, 0, 20, 0, 0, 70],
     [0, 20, 0, 80, 50, 0],
     [0, 0, 80, 0, 0, 30],
     [40, 0, 50, 0, 0, 60],
     [0, 70, 0, 30, 60, 0]];

print(nx.dijkstra_path(A, 0, 4))

在上面的代码中我直接使用了矩阵，但是库需要按如下方式创建图形

G = nx.Graph()
G = nx.add_node(<node>)
G.add_edge(<node 1>, <node 2>)

使用上述命令创建矩阵非常耗时。有什么方法可以将输入作为加权矩阵提供给 dijkstra_path 函数。

Answer 1

首先，您需要将邻接矩阵转换为具有 np.array 的 numpy 矩阵。然后你可以简单地用 from_numpy_matrix.

创建你的图表

import networkx as nx
import numpy as np

A = [[0, 100, 0, 0 , 40, 0],
     [100, 0, 20, 0, 0, 70],
     [0, 20, 0, 80, 50, 0],
     [0, 0, 80, 0, 0, 30],
     [40, 0, 50, 0, 0, 60],
     [0, 70, 0, 30, 60, 0]]

a = np.array(A)
G = nx.from_numpy_matrix(a)

print(nx.dijkstra_path(G, 0, 4))

输出：

[0, 4]

旁注：您可以使用以下代码检查图形边缘。

for edge in G.edges(data=True):
    print(edge)

输出：

(0, 1, {'weight': 100})
(0, 4, {'weight': 40})
(1, 2, {'weight': 20})
(1, 5, {'weight': 70})
(2, 3, {'weight': 80})
(2, 4, {'weight': 50})
(3, 5, {'weight': 30})
(4, 5, {'weight': 60})

在 networkx 库中使用 dijkstra_path 函数

Using dijkstra_path function in networkx library

dijkstra

shortest-path

networkx

adjacency-matrix

python-3.x