是否有可能让 networkx dijkstra 避免某些边缘？

Question

我有一个有向（或无向）非加权图的问题，我需要找到从 s 到 t 的简单路径。唯一的麻烦是我需要避开某些标记为红色的节点。

我找到了 python NetworkX 图形库，发现它非常合适。我想使用 networkx.dijkstra_path() （或者也可以使用 bfs 函数）来找到最短路径。

在这段代码中，我构建了一个非常简单的图，并找到了一条从 s = 0 到 t = 4 的路径：

import networkx


G = networkx.Graph()

for i in range(5):
    G.add_node(i)

# from zero
G.add_edge(0,1)
G.add_edge(0,3)

# from 1
G.add_edge(1,2)

# from 2
G.add_edge(2,4)

# from 3
G.add_edge(3,4)

path = networkx.dijkstra_path(G, 0, 4)

这个网络有这些节点： [0, 1, 2, 3, 4] 这些边： [(0, 1), (0, 3), (1, 2), (2, 4), (3, 4)] dijkstra 为我们提供了从 0-4 的这条路径： [0, 3, 4] 该图在视觉上看起来像这样（用 matplotlib 制作）：

但现在我想说节点 3 是红色的。所以我们需要避免它。这将使最短路径 [0,1,2,4]。有什么方法可以阻挡节点 3 以便 dijkstra 可以避开它吗？

Answer 1

我不知道有任何内置函数可以执行此操作。不过，您可以尝试以下步骤来获得想要的结果：

添加节点属性，您将在创建图表时根据该属性过滤节点。
过滤节点并创建子图。

在新子图上调用 Dijkstra 函数

import networkx 

G = networkx.Graph()

#Add an attribute color
for i in range(5):

    if i==3:
        G.add_node(i, color='red')
    else:
        G.add_node(i, color='blue')

# Add edges
G.add_edge(0,1)
G.add_edge(0,3)
G.add_edge(1,2)
G.add_edge(2,4)
G.add_edge(3,4)

# Functin to get filtered subgraph
def get_filtered_graph(G, ignore_attribute, ignore_val):
    # Filter the nodes based on the node attribute and value
    # In this case it is red color
    filtered_nodes = [x for x,y in G.nodes(data=True)
                   if y[ignore_attribute]!=ignore_val]

    # Create the subgraph
    H = G.subgraph(filtered_nodes)
    return H

ignore_attribute ='color'
ignore_val = 'red'
path = networkx.dijkstra_path(get_filtered_graph(G, filter_attribute, filter_val), 0, 4)

print(path)
# [0, 1, 2, 4]

参考文献：

Select Nodes and edges with attributes
NetworkX - Add Node

Answer 2

您可以使用single_source_dijkstra函数，对权重进行过滤：

为链接到节点 3 的边设置 'red' 属性
使用代码：

length, path = networkx.single_source_dijkstra(G, 0, 4, weight=lambda u, v, d: 1 if d['color']!="red" else None)

是否有可能让 networkx dijkstra 避免某些边缘？

is it possible to get networkx dijkstra to avoid certain edges?

python

graph

dijkstra

networkx