0

我有一个问题，我有一个有向（或非有向）非加权图，我需要找到从 st 开始的简单路径。唯一的复杂之处是我需要避免某些标记为红色的节点。

我找到了 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 可以避免它？

4

2 回答 2

0

我不知道有任何内置功能可以做到这一点。但是，您可以尝试以下步骤来获得所需的结果：

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

  • 过滤节点并创建子图。

  • 在新子图上调用 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]

参考：

于 2020-11-02T10:53:24.930 回答
0

您可以使用single_source_dijkstra函数，以及权重过滤函数：

  • 为链接到节点 3 的边设置“红色”属性
  • 使用代码：
length, path = networkx.single_source_dijkstra(G, 0, 4, weight=lambda u, v, d: 1 if d['color']!="red" else None)
于 2021-12-01T12:00:38.773 回答