Skip to main content
 首页 » 编程设计

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

2025年05月04日9mengfanrong

假设我有一个非循环的有向图 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 

请您参考如下方法:

'''

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

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

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

注意:我不确定问题规范是否完全正确,因为 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'])