通过两类节点的最优路径，这两类节点分别接触第一类和第二类的每个节点

Question

我试图解决一个复杂的问题，我相信它可以简化为求解一个加权无向图，如下所示。图形实际上会有多条平行边，尽管这里只显示了一条边。
S1 / \ 3 / \ 1 / \ A----1---B---100---S3 | | 10 10 | | D----1---C \ / 3 \ / 1 \ / S2

有两种类型的节点：
{S1，S2，S3}
{A，B，C，D}

答案将是将{A，B，C，D}中的节点连接到1且仅连接{S1，S2，S3}中的1的最小代价路径的最佳集合。“S”型节点是可选的，因为如果成本最低的路径是从S1-A-B-C-D开始的，而不使用S2或S3，这是正确的。但是，不能存在不包含1个且仅包含1个“S”类型节点的路径。你知道吗

上图将直观地解为2条路径：
S1 -> B -> A
S2 -> C -> D

S3不会连接到任何东西。你知道吗

如前所述，这是一个更大问题的简化，但我对图论相当陌生，不确定最好的方法来解决这个问题。你知道吗

此外，如果有一种简单的方法可以使用networkxpython库来实现这一点，那么我将使用networkxpython库。你知道吗

Answer 1

请注意-这只是正确答案的近似值。如果您有答案，请张贴：

这个答案的问题是：让我们看一个由s，a，B组成的三角形，s-a的权重为1，s-B的权重为1.5，a-B的权重为1。取决于你所说的最优：你可能认为总重量为2的S-B-A比总重量为2.5的S-B，S-A好。这个答案将给出到每个节点的最短路径，而不是全局最小路径。你知道吗

import networkx as nx
G=nx.Graph()
G.add_edges_from([('S1','A',{'weight':2.5}), ('S1','B', {'weight':1}), ('A','D',{'weight':10}), ('B','S3',{'weight':100}), ('B','C',{'weight':10}), ('A','B',{'weight':1}), ('D','C',{'weight':1}), ('D','S2',{'weight':2.5}), ('C','S2',{'weight':1})])
for S in ['S1', 'S2', 'S3']:
    G.add_edge('x', S, {'weight':0})
paths = nx.single_source_dijkstra(G,'x')
paths
>({'A': 2, 'B': 1, 'C': 1, 'D': 2, 'S1': 0, 'S2': 0, 'S3': 0, 'x': 0},
  {'A': ['x', 'S1', 'B', 'A'],
  'B': ['x', 'S1', 'B'],
  'C': ['x', 'S2', 'C'],
  'D': ['x', 'S2', 'C', 'D'],
  'S1': ['x', 'S1'],
  'S2': ['x', 'S2'],
  'S3': ['x', 'S3'],
  'x': ['x']})

注意，我将一些权重从2更改为2.5以避免歧义（在您的示例中，有多个cost2路径指向“A”）。你知道吗

现在，任何包含在另一条路径中的路径都可以被抛出。因此，遍历路径并跟踪在最终节点之前到达的任何节点。你知道吗

removable_nodes = set({})
for (target,path) in paths[1].items():
    for node in path[2:-1]:
        removable_nodes.add(node)
removable_nodes
> {'B', 'C'}

这意味着您需要的路径是指向“A”和“D”的路径。你知道吗