加权和有向二维 pandas csv 图中从 A 到 B 的最短路径

Question

我有一个由 2D n x n 矩阵表示的加权图，我使用 pandas 创建并保存为 csv 文件

索引和列headers是代表节点的数字。边是连接两个节点的权重

例如：{1232: {1232:inf, 2342:12, 45654:inf, 45678:21}}等等

我想实现 shortestRoute 算法，该算法将 return 从节点 a 到 b 的最短（总重量最小）路径的节点。

所以它将 return 1232 -> 2345 -> 45678

我知道我可以实现 Dijkstra 来获得最小的权重，但不确定如何获得路径

inf指的是没有边连接的两个节点

Answer 1

使用您的数据 + 一条额外的边做一个小例子。

import pandas as pd
import networkx as nx

so = pd.DataFrame({
    "source": [1232, 1232 , 1232, 2345 ],
    "target": [2342, 45678, 2345, 45678],
    "weight": [12  , 21   ,    1,      1]
})

G = nx.from_pandas_edgelist(so, source="source", target="target", edge_attr="weight")

# added since `nx.draw_networkx_edge_labels` requires `pos`
pos = nx.spring_layout(G)

nx.draw(G, pos=pos, with_labels=True, node_size=500)

# taken from 
nx.draw_networkx_edge_labels(G, pos=pos);

nx.shortest_path(G, source=1232, target=45678, weight="weight", method="dijkstra")
# >>> [1232, 2345, 45678]

加权和有向二维 pandas csv 图中从 A 到 B 的最短路径

Shortest path from A to B in a weighted and directed 2D pandas csv graph

python

pandas

graph

dijkstra