從元組在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

回答

相關問題