İki taraflı ağırlıklı bir grafikte en ucuz yol DFS/Açgözlü BFS

Question

İki taraflı ağırlıklı bir grafiğim var (tam olarak bir atama problemi) ve en ucuz yol/seçimi bulmak istiyorum. Yolu başarmak için DFS veya Greedy BFS'yi nasıl uygulayacağımı biliyor musunuz?

Bir adiacency listesi olarak temsil grafiği var (ya da ben en iyisi olacağını düşünüyorum) ne istiyorum mümkün mü bu ve DFS algoritması

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 

gibi? Sonuç şöyle olmalıdır: AWBXCYDZ veya en ucuz toplamı olan bir şey.

Ya da tüm olası geçişleri kökünden alabilir miyim? Bu DFS sadece bana bir tane verir ama ben tüm olası tranversalları istiyorum istiyorum

Answer 1

BFS veya DFS özellikle ağırlıklı grafikte en kısa yol arama için tasarlanmamıştır.

En ucuz yolu bulmak dijkstra veya A* algoritmaları ile gerçekleştirilebilir. Networkx, bu görev için bir full API sağlar.

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