[已解決] Python 找出路徑

python3

win895564 2022-08-03 17:02:44 ‧ 1421 瀏覽

分享至

目前在學Pyqgis
想實現的功能是給一個起點跟結束start=A end=H
line_dict={
'A':[['B','C']],
'B':[['A','C']],
'C':[['A','B'],['E','F','G']],
'E':[['C','F','G'],['I','H']],
'F':[['C','E','G']],
'I':[['H','E']],
'H':[['I','E']],
'G':[['E','F','C']]}
每條線是dictionary value為相連的線id
可以順利找到路徑但是會有些bug
走過的線都加進去
紅色的圈是交接點不需管黃色的點
紅色線上面的字母對應的是原始資料line_dict的key ,value是紅色圈交接點所交接的紅線英文字母ID
有嘗試過但是答案有些出入

start,end=A,H
road,tmp=[start],start

layer.removeSelection()

while tmp!=end:
    for i in line_dict[tmp]:
        for j in i :
            print(f"開始點{road[-1]} 有{len(i)}個交接點:{i}")
            if j not in road:
                
                
                road.append(j)
                tmp=j

print(f"最終路徑為:{road}")
layer.select(road)

起點為A 終點為H
提供思路也行小弟再來思考看看 ~ 感謝大大
output 為A-->C-->E-->H

登入發表討論

直播研討會

{{ item.channelVendor }} {{ item.webinarstarted }} |

直播中

2 個回答

I code so I am

iT邦高手 1 級 ‧ 2022-08-04 08:55:59

最佳解答

程式採用遞迴，修改如下：

# data
line_dict={
    'A':[['B','C']],
    'B':[['A','C']],
    'C':[['A','B'],['E','F','G']],
    'E':[['C','F','G'],['I','H']],
    'F':[['C','E','G']],
    'I':[['H','E']],
    'H':[['I','E']],
    'G':[['E','F','C']]
}

# 整理 line_dict 的 value
line_dict_flatten = {}
for k, v in line_dict.items():
    new_list = []
    for item in v:
        new_list += item
    line_dict_flatten[k] = new_list
print(line_dict_flatten)

# 尋找可行路徑
start_node,end_node='A','H'
road,current_node=[start_node],start_node
max_nodes = 10

all_feasible_path = []
# 遞迴
def find_next(node, path):
    if len(path)>=max_nodes: return
    for next_node in line_dict_flatten[node]:
        if next_node != end_node:
            path2 = path.copy()
            path2.append(next_node)
            #print(path2)
            find_next(next_node, path2)
        else:
#             if ''.join(path) == "ACE":
#             print(path + [next_node])
            all_feasible_path.append(path + [next_node])
            return   

find_next(current_node, road)

# 找最短路徑
print(min(all_feasible_path, key=lambda x: len(x)))

回應 3
分享
檢舉

win895564 iT邦研究生 5 級 ‧ 2022-08-04 09:37:17 檢舉

真的很感謝這位大大
因為資料原格式我這邊還可以修改
所以我不要以list of list來做這個會好寫很多是嘛

另外想請教一下大大這個寫法
只能以目前這個題目來解
還是可以隨題目變化
謝謝~

有機會的話希望能請您吃個飯

I code so I am iT邦高手 1 級 ‧ 2022-08-04 16:45:57 檢舉

【遞迴】適用於迴圈不知有多少層的狀況，多數程式語言均支援。
遞迴可隨題目不同而變化。

win895564 iT邦研究生 5 級 ‧ 2022-08-05 13:39:01 檢舉

瞭解了

登入發表回應

nitekat

iT邦新手 5 級 ‧ 2022-08-04 15:03:32

兩種作法供參考

def shortest_path(start, target):
    seen = set()
    queue = [(start, [])]

    while queue:
        node, history = queue.pop(0)
        if node == target:
            return history + [node]
        if node in seen:
            continue
        seen.add(node)
        for n in nodes_info[node]:
            queue.append((n, history + [node]))


line_dict = {
    "A": [["B", "C"]],
    "B": [["A", "C"]],
    "C": [["A", "B"], ["E", "F", "G"]],
    "E": [["C", "F", "G"], ["I", "H"]],
    "F": [["C", "E", "G"]],
    "I": [["H", "E"]],
    "H": [["I", "E"]],
    "G": [["E", "F", "C"]],
}

# 將原始資料攤平
nodes_info = {key: [item for sub in val for item in sub] for key, val in line_dict.items()}

print(shortest_path("A", "H"))

如果懶惰的話，可以用 networkx

import networkx as nx

line_dict = {
    "A": [["B", "C"]],
    "B": [["A", "C"]],
    "C": [["A", "B"], ["E", "F", "G"]],
    "E": [["C", "F", "G"], ["I", "H"]],
    "F": [["C", "E", "G"]],
    "I": [["H", "E"]],
    "H": [["I", "E"]],
    "G": [["E", "F", "C"]],
}

# 將原始資料攤平
nodes_info = {key: [item for sub in val for item in sub] for key, val in line_dict.items()}

g = nx.DiGraph()

for node in nodes_info:
    for node2 in nodes_info[node]:
        g.add_edge(node, node2)

print(nx.shortest_path(g, "A", "H"))