Günstigster Pfad in einem bipartiden gewichteten Diagramm DFS/Greedy BFS

Question

Ich habe einen bipartiden gewichteten Graphen (genauer ein Zuordnungsproblem) und möchte den günstigsten Pfad/Auswahl finden. Irgendeine Idee, wie ich DFS oder Greedy BFS implementieren würde, um den Pfad zu erreichen?

Ich habe die Grafik als adiacency Liste dargestellt (oder so glaube ich, am besten wäre) wie dieser und der DFS-Algorithmus

adjlist = {"A": ["W", "X"], 
      "B": ["W", "X", "Y", "Z"], 
      "C": ["Y", "Z"], 
      "D": ["W", "X", "Y", "Z"], 
      "W": ["A", "B", "D"], 
      "X": ["A", "B", "D"], 
      "Y": ["B", "C", "D"], 
      "Z": ["B", "C", "D"] } 

def dfser(graph, root): 
    visited =[] 
    stack = [root, ] 

    while stack: 
     node = stack.pop() 
     if node not in visited: 
      visited.append(node) 
      stack.extend([x for x in graph[node] if x not in visited]) 
    return visited 

Ist es möglich, was ich will? Das Ergebnis muss so aussehen: AWBXCYDZ oder etwas mit der billigsten Summe.

Oder kann ich alle möglichen Traversals von Root bekommen? Dieses DFS gibt mir nur einen, aber ich möchte alle möglichen Transversale

Answer 1

BFS oder DFS sind nicht für die kürzeste Pfadsuche, vor allem in einem gewichteten Graphen entwickelt.

Die Suche nach dem günstigsten Pfad könnte mit den dijkstra oder A* Algorithmen durchgeführt werden. Networkx stellt für diese Aufgabe full API zur Verfügung.

Das NetworkX Modul implementiert bipartite graphs und zugehörige Algorithmen:

Dicti = {"A": {"W": 2, "X": 2}, 
    "B": {"W": 4, "X": 3, "Y": 2, "Z": 5}, 
    "C": {"Y": 2, "Z": 2}, 
    "D": {"W": 5, "X": 5, "Y": 4, "Z": 3}, 
    "W": {"A": 2, "B": 4, "D": 5}, 
    "X": {"A": 2, "B": 3, "D": 5}, 
    "Y": {"B": 2, "C": 2, "D": 4}, 
    "Z": {"B": 5, "C": 2, "D": 3} 
} 

graph = nx.Graph() 
for node, succs in Dicti.items(): 
    for succ, weight in succs: 
     graph.add_edge(node, succ, weight=weight) 

print(nx.dijkstra_path(graph, 'A', 'Z')) # here is Dijkstra