Wie berechne ich die Länge eines Pfades aus einem gewichteten Diagramm in Python?

Question

Ich mache dieses Projekt und habe ein Problem herauszufinden, welcher Pfad die kürzeste Länge hat. Das Setup ist ein Supermarkt. Du fängst am Eingang an und gehst am Gelddeck aus. Die Punkte A, B, C, D sind die Punkte in den Sektionen im Supermarkt wie der Bake-Off etc. Am Eingang 'via' können Sie die Punkte angeben, die Sie passieren möchten.

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

Der Ausgang:

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']] 

Aber ich habe keine Ahnung, wie ich die Länge eines jeden gefundenen Pfad berechnen kann und wie kann ich die kürzeste aus diesen.

Answer 1

Sie müssen die Pfadlängen sammeln, während Sie die Pfade erstellen. Es ist möglich, Ihren vorhandenen Code zu ändern, um dies zu tun, aber es wird unordentlich. Ein sauberer Weg, dies zu tun, besteht darin, Ihre Funktion in einen Generator umzuwandeln, so dass sie Pfade liefert, sobald sie sie finden, anstatt sie in einer Liste von Pfaden zu speichern.

Wir können die Generatorausgabe an die sorted Funktion übergeben, um eine Liste der Pfade sortiert nach ihrer Länge zu erhalten.

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) 

Ausgang

['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 

Ein anderer Weg, um die find_all_paths Generator zu nennen, ist

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) 

diese Weise können wir die unerwünschten Pfade filtern, bevor sie sortiert bekommen. Und wenn Sie nur den kürzesten Pfad wünschen, können Sie den Anruf zu sorted mit min ersetzen.

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

Ausgang

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

---

ich ein paar andere kleine Änderungen an Ihrem Code vorgenommen haben.

Wenn der Benutzer gibt nichts an der 'via' Prompt dann wird required auf eine Liste setzen Sie die leere Zeichenfolge, und das wird vermasseln Ihre exists_in_graph Test enthalten, so dass wir required auf die leere Liste gesetzt, wenn das passiert.

In Ihrer Version von find_all_paths geben Sie path einen Standardwert der leeren Liste. Das wird Dinge durcheinander bringen, wenn Sie mehr als einmal find_all_paths aufrufen möchten, weil Standardargumente ausgewertet werden, wenn die Funktion erstellt wird, nicht wenn sie aufgerufen wird. Also, wenn Sie find_all_paths erneut aufrufen, ohne eine path Arg zur Verfügung zu stellen, wird es die gleiche Standard path Liste verwenden, die es ursprünglich verwendete, es wird nicht eine neue leere Liste verwenden. Der übliche Weg, um damit umzugehen, ist, einen Standard von None zu verwenden, wie ich es in meinem Code getan habe. Weitere Informationen zu diesem wichtigen Thema finden Sie unter “Least Astonishment” and the Mutable Default Argument.