从Python中的元组列表中查找路径

问题内容：

我有以下形式的元组列表：

data = [('Abe', 'Bob', '3'), 
        ('Abe', 'Frank', '5'),
        ('Abe', 'George', '4'),
        ('Carl', 'Bob', '1'),
        ('Dan', 'Carl', '2')]

此数据模拟无向图，其中从’Abe’到大小为3的’Bob’之间存在联系。由于该图是无向的，因此也意味着从’Bob’到大小为3的’Abe’之间存在联系。好。

我需要显示两个输入之间是否存在连接及其权重。例如，如果输入为“ Abe”，“ Dan”，则结果将返回从“ Abe”到“
Dan”的最短路径（最小节点跳，不是最不重要的权重），该路径为Abe，Bob，Carl，Dan和权重3 + 1 + 2 = 6。

我有这段代码显示“ Abe”是否会到达“ Dan”，但是我不知道如何返回路径。

def get_path_and_weight(data, start, end):

    reachable = [start]
    added = -1

    while added != 0:
        added = 0
        for first, second, weight in data:
            if(first in reachable) and (second not in reachable):
                reachable.append(second)
                added += 1
            if(first not in reachable) and (second in reachable): 
                reachable.append(first)
                added += 1

        if (end in reachable):
            print("YES")
            #return path
        else:
            print("NO")

问题答案：

您可以生成所有可能的路径，然后按权重对其进行排序。注意我已经将数据中的权重更改为数字，而不是字符串：

data = [
    ('Abe', 'Bob', 3), 
    ('Abe', 'Frank', 5),
    ('Abe', 'George', 4),
    ('Carl', 'Bob', 1),
    ('Dan', 'Carl', 2),
]

WEIGHT = 0
NODES = slice(1, None)

def get_path_and_weight(data, start, end):

    paths = [[0, start]]
    added = True

    while added:
        added = False

        for first, second, weight in data:
            for path in paths:
                candidate = None

                if (first in path[NODES]) and (second not in path[NODES]):
                    candidate = second
                elif (first not in path[NODES]) and (second in path[NODES]):
                    candidate = first

                if candidate:
                    new_path = list(path)
                    new_path.append(candidate)
                    new_path[WEIGHT] += weight

                    if new_path not in paths:
                        paths.append(new_path)
                        added = True

    for path in sorted(paths):
        if end in path[NODES]:
            return path

    return None

然后，您可以将其命名为：

weight, *path = get_path_and_weight(data, "Abe", "Dan")

print(path, "with weight", weight)

给出结果：

['Abe', 'Bob', 'Carl', 'Dan'] with weight 6

并且由于它返回路径or None，因此您仍然可以将其用作谓词函数：

if get_path_and_weight(data, "Abe", "Dan"):
    print("connected")

从Python中的元组列表中查找路径

微信关注