为什么图找不到正确的路径？

Question

我尝试在以下 link 的帮助下创建图表，但是当我使用 find_path 方法时，我返回了错误的路径。 Link:

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

Graph class 中的 find_path 方法有什么问题？

Answer 1

您将其编程为查找任何非循环路径，并且 return 它找到的第一个。它找到的路径是完全合理的；这根本不是最少的步骤。

要找到最短路径，您需要实施广度优先搜索或带记忆的深度优先搜索（跟踪每个节点的最佳已知路径）。 Dijkstra 算法适用于最短路径。

Answer 2

您的代码正在通过跟踪每个节点的邻接列表中尚不属于图中的第一个节点来查找路径。它从 'b' 开始，然后转到邻接列表中的第一个节点 (['a', 'c']) 节点 'a'。然后从 'a' 到 'c'。一旦到达 'c'，它会发现 'a'、'b' 和 'c' 已经在路径中，因此它会转到 'd'。如果您将图中邻接表的顺序更改为此，它将打印出您要查找的顺序：

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

或者，您可以实现最短路径算法，例如 Djikstra's 以找到通过图形的最短路径。

为什么图找不到正确的路径？

Why graph doesn't find correct path?

python

traversal

graph

path

edge-list