从元组在Python

列表查找路径我有如下形式的元组的列表：从元组在Python

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

此数据模拟了一个无向图，其中有来自“安倍晋三”到“鲍勃”的连接大小3.因为图是无向的，所以也意味着从“Bob”到大小为3的“Abe”也有连接。

我需要显示两个输入之间是否存在连接以及它的重量是多少。例如，如果输入是'Abe'，'Dan'，结果将返回从'Abe'到'Dan'的最短（最小节点跳数，不是最小重量）路径，这将是Abe，Bob，Carl，Dan和重量，3 + 1 + 2 = 6.

我有这个代码显示'Abe'是否会达到'丹'，但我不知道如何返回路径。

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")

来源

2016-03-14 CS student

确定算法本身是正确的几个包？也许你找不到路径的原因是你没有真正检查它。检查它是否已断开连接。一眼就可以回答一个顶点是否在图中。你想要做的是广度优先搜索或深度优先搜索。 – luk32

我还没有喝过咖啡，但我的第一个想法是只做Dijkstra，其伪边权重为1，这将为您提供从一个节点到另一个节点的跳数最少的路径。然后添加稍后使用的边的实际权重。 – timgeb

您可以生成所有可能的路径，并按重量对它们进行排序。请注意我的数据改变了权重是数字，而不是字符串：

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

并且由于它返回一条路径或None，所以仍然可以将其用作谓词函数：

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

来源

2016-03-14 07:34:28 cdlane

-1

def get_rpath_with_weight(data,start,end): 
    rpath = [] 
    reachable=False 
    nxt_dst = start 
    weight_ = 0 
    rpath.append(nxt_dst) 
    for datum in data: 
     if nxt_dst in datum: 
      #print datum 
      fm_ = datum[0] 
      to_ = datum[1] 
      weight_ = weight_ + int(datum[2]) 
      if fm_ == nxt_dst: 
       nxt_dst = to_ 
      else: 
       nxt_dst = fm_ 
      if nxt_dst == end: 
       reachable=True 
      rpath.append(nxt_dst) 
    print rpath,weight_,reachable 


get_rpath_with_weight(data,'Abe','Dan') 

get_rpath_with_weight(data,'Dan','Frank')

样本输出

['Abe', 'Bob', 'Carl', 'Dan'] 6 True 
['Dan', 'Carl'] 2 False

上面的例子中可能得到的路径，如果到达确定，但我认为你需要进一步提高它来处理多个路径了。

来源

2016-03-14 07:25:42

这里似乎存在一个错误，如果你反转开始和结束，'get_rpath_with_weight（data，'Dan'，'Abe'）'你应该得到相同的基本结果，只是路径颠倒，而是你会得到：' ['丹'，'卡尔'] 2假' – cdlane

是的，因为这个例子只是想激励而不是给予和回答，反向路径和多路径没有处理。也许以后。 :) –

有迹象表明，已经开发和调试的是做到这一点，例如，networkx

import networkx as nx 

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

g = nx.Graph() 
for e in data: 
    g.add_edge(e[0], e[1], distance=int(e[2])) 
>>> nx.shortest_path(g, 'Abe', 'Bob', 'distance'), nx.shortest_path_length(g, 'Abe', 'Bob', 'distance') 
(['Abe', 'Bob'], 3)

来源

2016-03-14 07:35:54

从元组在Python

回答

相关问题