python - 在 Python 中查找小于或等于非循环有向图的给定值的最长路径

Question

假设我有一个非循环的有向图 G，节点为 a0, a1, a2, b0, b1, b2, c0, c1, c2 并且我知道每个节点到它的任何邻居的传出距离。我可以使用什么算法来找到任意两个节点之间小于给定长度的最长路径？

编辑:我看过 Wikipedia page对于最长路径问题，但我不知道是使用“非循环图和关键路径”部分中概述的算法还是“参数化复杂性”部分中的算法。这两种情况我都会遇到问题。在前者中，算法要求你有传入距离(我有传出距离)，老实说，后者的描述在实现方面超出了我的理解范围。

EDIT2:我完成的图如下

graph = {
             "a0": set(["a1", "b0])
             "a1": set(["a2", "b1"])
             "a2": set(["b2"])
             "b0": set(["b1", "c0"])
             "b1": set(["b2", "c1"])
             "b2": set(["c2"])
             "c0": set(["c1"])
             "c1": set(["c2"])
             "c2": set([])
}

我在单独的字典中也有传出距离，例如

edge_distance = {
                 "a0": 0
                 "a1": 4
                 "a2": 12
                 "b0": 2
                 "b1": 1
                 "b2": 4
                 "c0": 7
                 "c1": 2
                 "c2": 1
}

从技术上讲，我有传入距离的唯一节点是 c2

我要找的路径是a0到c2

EDIT3:我的图表，拓扑排序:

   c2 b2 c1 a2 b1 c0 a1 b0 a0

Answer 1

'''

这符合给定的问题规范，除了它显示两点之间的所有距离。选择低于某个阈值的最大的一个是微不足道的。

它根本没有优化，也不是通用的，因为给定的问题规范对于离开任何特定节点的每条边都有一个单一的距离。尽管如此，它应该很容易修改以使其更通用。

此外，主要变量是全局变量，但这也很容易补救。

注意:我不确定问题规范是否完全正确，因为 a0 的距离给出为 0，但 c2(不连接任何地方)的距离给出为 1。无论如何该场景(和示例代码)非常人为设计，因为离开给定节点的所有边在现实生活中不太可能具有相同的长度。

'''

如果 1:

import collections

# Data given in problem description

# Keys are starting nodes, values are destination nodes.

graph = {
            "a0": set(["a1", "b0"]),
            "a1": set(["a2", "b1"]),
            "a2": set(["b2"]),
            "b0": set(["b1", "c0"]),
            "b1": set(["b2", "c1"]),
            "b2": set(["c2"]),
            "c0": set(["c1"]),
            "c1": set(["c2"]),
            "c2": set([]),
}

# Length of every outbound edge from the node

edge_distance = {
                "a0": 0,
                "a1": 4,
                "a2": 12,
                "b0": 2,
                "b1": 1,
                "b2": 4,
                "c0": 7,
                "c1": 2,
                "c2": 1,
                }

def sort_graph():
    ''' Develop a sorted list using Kahn's algorithm
    '''
    # Number of incoming vertices to each node
    incoming = collections.defaultdict(int)

    #All nodes with vertices exiting them
    startnodes = set()

    # All nodes with vertices entering them
    endnodes = set()

    for start in graph:
        for end in graph[start]:
            startnodes.add(start)
            endnodes.add(end)
            incoming[end] += 1

    ordered = []
    startnodes -= endnodes
    while startnodes:
        start = startnodes.pop()
        ordered.append(start)
        for end in graph[start]:
            incoming[end] -= 1
            if not incoming[end]:
                startnodes.add(end)
    if sum(incoming.values()):
        raise ValueError("Graph has at least one cycle")

    return ordered

ordered = sort_graph()

def calc_dists(start):
    ''' Returns a dictionary containing all possible
        distances from a given start node to each other
        node, expressed as a set of possible distances
        for each target node.  The set will be empty
        if the target node is not reachable from the
        start node.
    '''
    dist_to_node = collections.defaultdict(set)
    dist_to_node[start].add(0)
    for start in ordered:
        cumulative = dist_to_node[start]
        dist = edge_distance[start]
        for end in graph[start]:
            dist_to_node[end].update(dist + prev for prev in cumulative)
    return dist_to_node

# Show all possible distances between a0 and c2
print(calc_dists('a0')['c2'])