그래프가 올바른 경로를 찾지 못하는 이유는 무엇입니까?

Question

다음 링크를 사용하여 그래프를 만들려고했지만 find_path 메서드를 사용했을 때 잘못된 경로가 반환되었습니다. 링크 :

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

코드 : 그래프 클래스의 find_path 방법 뭐가 문제

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

?

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

비주기 경로를 찾고 찾은 첫 번째 경로를 반환하도록 프로그래밍했습니다. 발견 된 경로는 완벽하게 합리적입니다. 단순히 최소한의 단계 만은 아닙니다.

최단 경로를 찾으려면 너비 우선 검색 또는 메모로 깊이 우선 검색 (각 노드에 가장 잘 알려진 경로 추적)을 구현해야합니다. Dijkstra의 알고리즘은 최단 경로에 유용합니다.