Pourquoi le graphique ne trouve pas le chemin correct?

Question

J'ai essayé de créer un graphique à l'aide du lien suivant, mais lorsque j'ai utilisé la méthode find_path, j'ai obtenu un chemin incorrect. Lien:

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

code:

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

Quel est le problème avec la méthode find_path en classe graphique?

Answer 1

Votre code recherche le chemin en suivant le premier nœud de la liste d'adjacence de chaque nœud qui n'appartient pas déjà au graphique. Il commence à 'b' et passe ensuite au premier nœud de la liste d'adjacence (['a', 'c']) nœud 'a'. Ensuite, il passe de 'a' à 'c'. Une fois qu'il est à 'c', il voit que 'a', 'b', et 'c' sont déjà dans le chemin de sorte qu'il va à 'd'. Si vous avez changé l'ordre de votre liste de contiguïté dans le graphique à cela, il affichera l'ordre de votre recherche:

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

Vous pouvez également mettre en œuvre un algorithme de chemin le plus court, comme Djikstra's pour trouver le chemin le plus court à travers un graphique.

Answer 2

Vous avez programmé ceci pour trouver un chemin acyclique, et retourner le premier qu'il trouve. Le chemin qu'il a trouvé est parfaitement raisonnable; ce n'est tout simplement pas le moindre nombre de pas.

Pour trouver le chemin le plus court, vous devez implémenter soit une recherche en largeur d'abord, soit une recherche en profondeur en profondeur avec mémorisation (garder trace du chemin le plus connu vers chaque nœud). L'algorithme de Dijkstra est bon pour le chemin le plus court.