파이썬에서 가중 그래프의 경로 길이를 어떻게 계산합니까?

Question

나는이 프로젝트를하고 있는데 어떤 경로가 가장 짧은 길이인지 알아 내는데 문제가있다. 설정은 슈퍼마켓입니다. 입구에서 시작하면 현금 데크에서 나옵니다. 점 A, B, C, D는 베이크 오프 (bake-off) 등 슈퍼마켓의 섹션에있는 점입니다. 'via'입력에서 전달하려는 점을 제공 할 수 있습니다.

#e = entrance 
#k = cash desk 
graph1 = {'e':{'a':1, 'b':5, 'c':6, 'd':6}, 
    'a':{'e':2, 'b':4, 'c':5, 'd':5, 'k':7}, 
    'b':{'e':5, 'a':5, 'c':3, 'd':5, 'k':6}, 
    'c':{'e':6, 'a':5, 'b':3, 'd':4, 'k':5}, 
    'd':{'e':6, 'a':3, 'b':5, 'c':4, 'k':2}, 
    'k':{'a':7, 'b':6, 'c':5, 'd':2} 
} 

start = input('start') 
end = input('end') 
required = input('via').split(',') 

def find_all_paths(graph, start, end, path=[]): 
    path = path + [start] 
    if start == end: 
     return [path] 
    if not start in graph: 
     return [] 
    paths = [] 
    for node in graph[start]: 
     if node not in path: 
      newpaths = find_all_paths(graph, node, end, path) 
      for newpath in newpaths: 
       paths.append(newpath) 
    return paths 

def exists_in_graph(graph, nodes): 
    for node in nodes: 
    if not node in graph: 
     return False 
    return True 

allPaths = find_all_paths(graph1, start, end) 
allPathsTroughNodes = list(filter(lambda x: exists_in_graph(x, required), 
allPaths)) 
print(allPathsTroughNodes) 

출력 :

start e 
end k 
via a,c,d 
[['e', 'a', 'b', 'c', 'd', 'k'], ['e', 'a', 'b', 'd', 'c', 'k'], ['e', 'a', 
'c', 'b', 'd', 'k'], ['e', 'a', 'c', 'd', 'b', 'k'], ['e', 'a', 'c', 'd', 
'k'], ['e', 'a', 'd', 'b', 'c', 'k'], ['e', 'a', 'd', 'c', 'b', 'k'], ['e', 
'a', 'd', 'c', 'k'], ['e', 'b', 'a', 'c', 'd', 'k'], ['e', 'b', 'a', 'd', 
'c', 'k'], ['e', 'b', 'c', 'a', 'd', 'k'], ['e', 'b', 'c', 'd', 'a', 'k'], 
['e', 'b', 'd', 'a', 'c', 'k'], ['e', 'b', 'd', 'c', 'a', 'k'], ['e', 'c', 
'a', 'b', 'd', 'k'], ['e', 'c', 'a', 'd', 'b', 'k'], ['e', 'c', 'a', 'd', 
'k'], ['e', 'c', 'b', 'a', 'd', 'k'], ['e', 'c', 'b', 'd', 'a', 'k'], ['e', 
'c', 'd', 'a', 'b', 'k'], ['e', 'c', 'd', 'a', 'k'], ['e', 'c', 'd', 'b', 
'a', 'k'], ['e', 'd', 'a', 'b', 'c', 'k'], ['e', 'd', 'a', 'c', 'b', 'k'], 
['e', 'd', 'a', 'c', 'k'], ['e', 'd', 'b', 'a', 'c', 'k'], ['e', 'd', 'b', 
'c', 'a', 'k'], ['e', 'd', 'c', 'a', 'b', 'k'], ['e', 'd', 'c', 'a', 'k'], 
['e', 'd', 'c', 'b', 'a', 'k']] 

그러나 내가 발견 된 각 경로의 길이를 계산할 수 있습니다 나는이 중 가장 짧은 하나를 얻을 수있는 방법을 어떻게 단서가 없다.

Answer 1

경로를 작성하는 동안 경로 길이를 누적해야합니다. 이를 수행하기 위해 기존 코드를 수정할 수도 있지만 엉망이됩니다. 이를 수행하는 더 깔끔한 방법은 함수를 생성기로 변환하여 경로 목록에 저장하는 대신 경로를 발견 한 경로를 생성하는 것입니다.

길이가 정렬 된 경로 목록을 얻기 위해 발전기 출력을 sorted 함수에 전달할 수 있습니다.

import sys 

graph1 = { 
    'e': {'a': 1, 'b': 5, 'c': 6, 'd': 6}, 
    'a': {'e': 2, 'b': 4, 'c': 5, 'd': 5, 'k': 7}, 
    'b': {'e': 5, 'a': 5, 'c': 3, 'd': 5, 'k': 6}, 
    'c': {'e': 6, 'a': 5, 'b': 3, 'd': 4, 'k': 5}, 
    'd': {'e': 6, 'a': 3, 'b': 5, 'c': 4, 'k': 2}, 
    'k': {'a': 7, 'b': 6, 'c': 5, 'd': 2} 
} 

#start = input('start ') 
#end = input('end ') 
#required = input('via ').split(',') 
#if required == ['']: 
    #required = [] 

# Hard-code some input data to make it easier to test the code 
start, end = 'e', 'k' 
required = [] 

def find_all_paths(graph, start, end, path=None, pathlen=0): 
    if path is None: 
     path = [] 
    path = path + [start] 
    if start == end: 
     yield pathlen, path 
    if not start in graph: 
     yield [], 0 
     return 

    for node, val in graph[start].items(): 
     if node not in path: 
      yield from find_all_paths(graph, node, end, path, pathlen + val) 

def exists_in_graph(graph, nodes): 
    for node in nodes: 
     if not node in graph: 
      return False 
    return True 

if not exists_in_graph(graph1, [start, end] + required): 
    print('Bad data!') 
    sys.exit() 

all_paths = sorted(find_all_paths(graph1, start, end)) 
for pathlen, path in all_paths: 
    if exists_in_graph(path, required): 
     print(path, pathlen) 

출력

['e', 'a', 'd', 'k'] 8 
['e', 'a', 'k'] 8 
['e', 'd', 'k'] 8 
['e', 'a', 'b', 'k'] 11 
['e', 'a', 'c', 'k'] 11 
['e', 'b', 'k'] 11 
['e', 'c', 'k'] 11 
['e', 'a', 'b', 'd', 'k'] 12 
['e', 'a', 'c', 'd', 'k'] 12 
['e', 'b', 'd', 'k'] 12 
['e', 'c', 'd', 'k'] 12 
['e', 'a', 'b', 'c', 'k'] 13 
['e', 'b', 'c', 'k'] 13 
['e', 'a', 'b', 'c', 'd', 'k'] 14 
['e', 'b', 'c', 'd', 'k'] 14 
['e', 'a', 'c', 'b', 'k'] 15 
['e', 'a', 'd', 'c', 'k'] 15 
['e', 'c', 'b', 'k'] 15 
['e', 'd', 'c', 'k'] 15 
['e', 'a', 'c', 'b', 'd', 'k'] 16 
['e', 'c', 'b', 'd', 'k'] 16 
['e', 'd', 'a', 'k'] 16 
['e', 'a', 'd', 'b', 'k'] 17 
['e', 'b', 'a', 'd', 'k'] 17 
['e', 'b', 'a', 'k'] 17 
['e', 'd', 'b', 'k'] 17 
['e', 'c', 'a', 'd', 'k'] 18 
['e', 'c', 'a', 'k'] 18 
['e', 'a', 'b', 'd', 'c', 'k'] 19 
['e', 'a', 'd', 'b', 'c', 'k'] 19 
['e', 'a', 'd', 'c', 'b', 'k'] 19 
['e', 'b', 'd', 'c', 'k'] 19 
['e', 'd', 'a', 'b', 'k'] 19 
['e', 'd', 'a', 'c', 'k'] 19 
['e', 'd', 'b', 'c', 'k'] 19 
['e', 'd', 'c', 'b', 'k'] 19 
['e', 'b', 'a', 'c', 'k'] 20 
['e', 'b', 'c', 'a', 'd', 'k'] 20 
['e', 'b', 'c', 'a', 'k'] 20 
['e', 'b', 'd', 'a', 'k'] 20 
['e', 'c', 'd', 'a', 'k'] 20 
['e', 'a', 'c', 'd', 'b', 'k'] 21 
['e', 'b', 'a', 'c', 'd', 'k'] 21 
['e', 'c', 'a', 'b', 'k'] 21 
['e', 'c', 'b', 'a', 'd', 'k'] 21 
['e', 'c', 'b', 'a', 'k'] 21 
['e', 'c', 'd', 'b', 'k'] 21 
['e', 'd', 'a', 'b', 'c', 'k'] 21 
['e', 'b', 'c', 'd', 'a', 'k'] 22 
['e', 'c', 'a', 'b', 'd', 'k'] 22 
['e', 'd', 'c', 'a', 'k'] 22 
['e', 'b', 'd', 'a', 'c', 'k'] 23 
['e', 'c', 'd', 'a', 'b', 'k'] 23 
['e', 'd', 'a', 'c', 'b', 'k'] 23 
['e', 'd', 'b', 'a', 'k'] 23 
['e', 'b', 'a', 'd', 'c', 'k'] 24 
['e', 'c', 'b', 'd', 'a', 'k'] 24 
['e', 'd', 'c', 'a', 'b', 'k'] 25 
['e', 'd', 'c', 'b', 'a', 'k'] 25 
['e', 'b', 'd', 'c', 'a', 'k'] 26 
['e', 'd', 'b', 'a', 'c', 'k'] 26 
['e', 'd', 'b', 'c', 'a', 'k'] 26 
['e', 'c', 'a', 'd', 'b', 'k'] 27 
['e', 'c', 'd', 'b', 'a', 'k'] 27 

find_all_paths 발전기를 호출하는 또 다른 방법은 분류하기 전에 우리가 원하지 않는 경로를 필터링 할 수 있습니다

valid_paths = sorted((pathlen, path) 
    for pathlen, path in find_all_paths(graph1, start, end) 
     if exists_in_graph(path, required) 
) 
for pathlen, path in valid_paths: 
    print(path, pathlen) 

그 방법입니다. 그리고 가장 짧은 경로를 원할 경우 sorted으로 전화를 바꿔 min으로 바꿀 수 있습니다.

pathlen, path = min((pathlen, path) 
    for pathlen, path in find_all_paths(graph1, start, end) 
     if exists_in_graph(path, required) 
) 
print(path, pathlen) 

내가 코드에 다른 작은 변화의 몇 가지를했습니다

['e', 'a', 'd', 'k'] 8 

---

출력. 그것이 우리가 빈리스트에 required를 설정 발생하는 경우 있도록

사용자가 다음 프롬프트 'via'required에 아무것도 입력하지 않으면

는 빈 문자열을 포함하는 목록, 그 의지 엉망 당신 exists_in_graph 테스트로 설정되어 있습니다.

find_all_paths 버전에서는 path에 빈 목록의 기본값이 제공됩니다. find_all_paths을 두 번 이상 호출하려고하면 기본 args가 호출 될 때가 아니라 함수가 작성 될 때 평가되기 때문에 문제가 해결됩니다. 따라서 path 인수를 제공하지 않고 find_all_paths을 다시 호출하면 원래 사용 된 동일한 기본 path 목록을 사용하게됩니다. 은에 새 빈 목록을 사용하지 않습니다. 이것을 처리하는 일반적인 방법은 내 코드에서 한 것처럼 기본값 인 None을 사용하는 것입니다. 이 중요한 주제에 대한 자세한 내용은 “Least Astonishment” and the Mutable Default Argument을 참조하십시오.