なぜグラフが正しいパスを見つけられないのですか？

Question

私は、次のリンクの助けを借りてグラフを作成しようとしましたが、find_pathメソッドを使用したときに不正なパスが返されました。リンク：

http://www.python-course.eu/graphs_python.php

コード：

class Graph(object): 
    def __init__(self, graph_dict=None): 
     """ initializes a graph object 
      If no dictionary or None is given, an empty dictionary will be used 
     """ 
     if graph_dict is None: 
      graph_dict = {} 
     self.__graph_dict = graph_dict 

    def find_path(self, start_vertex, end_vertex, path=[]): 
     """ find a path from start_vertex to end_vertex 
      in graph """ 
     graph = self.__graph_dict 
     path = path + [start_vertex] 
     if start_vertex == end_vertex: 
      return path 
     if start_vertex not in graph: 
      return None 
     for vertex in graph[start_vertex]: 
      if vertex not in path: 
       extended_path = self.find_path(vertex, 
               end_vertex, 
               path) 
       if extended_path: 
        return extended_path 
     return None 

g = {"a": ["c", "d"], 
    "b": ["a", "c"], 
    "c": ["a", "b", "c", "d", "e"], 
    "d": ["c", "e"], 
    "e": ["c", "f"], 
    "f": ["c"] 
    } 

graph = Graph(g) 

""" 
graph: 

a<----b   <-- one way 
|\ /  --- two way 
| \/
| c <-- f 
|/\ ^
v/ \ | 
d---->e--/ 

""" 
print graph.find_path("b", "f") 

Output: ['b', 'a', 'c', 'd', 'e', 'f'] 
Should be: ['b', 'a', 'd', 'e', 'f'] 

グラフクラスのfind_pathの方法が間違っていますか？

Answer 1

あなたのコードは、まだグラフに属していない各ノードの隣接リストの最初のノードをたどってパスを探しています。 'b'で始まり、次に隣接リスト（['a', 'c']）ノード'a'の最初のノードに進みます。その後、'a'から'c'になります。 'c'になると、'a','b'、および'c'がすでにパスに入っているので、'd'になります。最短経路を見つけるために、あなたがそのようなDjikstra'sとして最短経路アルゴリズムを実装することができ、また

g = {"a": ["d", "c"], 
    "b": ["a", "c"], 
    "c": ["a", "b", "c", "d", "e"], 
    "d": ["e", "c"], 
    "e": ["f", "c"], 
    "f": ["c"] 
    } 

：あなたはこれをグラフにあなたの隣接リストの順番を変更した場合、それはあなたが探して順序を出力しますグラフ。

Answer 2

の非循環パスを検索し、見つかった最初のものを戻すようにプログラムしました。見つけた道は完全に合理的です。それは単純に最小のステップ数ではありません。

最短経路を見つけるには、幅優先探索、または深度優先探索のメモ処理（各ノードへの最もよく知られた経路の追跡）を実装する必要があります。ダイクストラのアルゴリズムは、最短経路に適しています。