在循环加权图中查找最短路径

Question

我试图在循环加权图中找到最短路径。我有以下递归函数，如果它们不是循环的，它能够找到 2 点之间的最短路径。例如，我的图表如下所示：

graph = {
          'A': {'B': 5, 'D': 5, 'E': 7 },
          'B': {'C': 4},
          'C': {'D': 8, 'E': 2},
          'D': {'C': 8, 'E':  6},
          'E': {'B': 3}
        }

现在我的 find shortestRoute 函数如下所示

def findShortestRoute(self, start, end , weight, shortestRoute):
    # sys.setrecursionlimit(10000)
    visited = []
    # Check if start and end nodes exists in route table
    if start in self.routesTable and end in self.routesTable:
        visited.append(start) # mark start to visited

        for adj in self.routesTable[start]:
            if(adj == end or adj not in visited):
                weight += self.routesTable[start][adj]

            '''
            If destination matches, we compare
            weight of this route to shortest route
            so far, and make appropriate switch
            '''

            if adj == end:
                if shortestRoute == 0 or weight < shortestRoute:
                    shortestRoute = weight
                visited.remove(start)
                return shortestRoute
            '''
            If destination does not match, and
            destination node has not yet been visited,
            we recursively traverse destination node
            '''
            if adj not in visited:
                shortestRoute = self.findShortestRoute(adj, end, weight, shortestRoute)
                weight -= self.routesTable[start][adj]

    else:
        return "No such route exists"

    if start in visited:
        visited.remove(start)

    return shortestRoute

现在对于非循环情况，如果我做类似的事情

findShortestRoute('A', 'C', 0, 0)

这将 return 9 这是预期的。但是，如果我这样做 findShortestRoute('B', 'B', 0, 0)

函数将达到堆栈溢出。然而，由于图是循环的，所以有一种方法可以从 B 开始并返回到 B。在这种情况下，B-C-E-B 的权重为 9。但是我的函数正在达到最大递归。如果有人可以帮助我，我将不胜感激。提前致谢

Answer 1

您的问题是您没有通过递归传递 visited 列表，因此您的算法陷入了循环。如果你传递前任节点，你可以检测到循环，如果你击中一个 return。

这就是我将如何更改您的代码来实现此目的：

def findShortestRoute(start, end , weight, shortestRoute, visited, routesTable):
# sys.setrecursionlimit(10000)
# Check if start and end nodes exists in route table

if start in routesTable and end in routesTable:
    if start in visited:
        return 99999
    visited.append(start) # mark start to visited

    for adj in routesTable[start]:
        if(adj == end or adj not in visited):
            weight += routesTable[start][adj]

        '''
        If destination matches, we compare
        weight of this route to shortest route
        so far, and make appropriate switch
        '''

        if adj == end:
            if shortestRoute == 0 or weight < shortestRoute:
                shortestRoute = weight
            visited.remove(start)
            return shortestRoute
        '''
        If destination does not match, and
        destination node has not yet been visited,
        we recursively traverse destination node
        '''
        if adj not in visited:
            shortestRoute = findShortestRoute(adj, end, weight, shortestRoute, visited, routesTable)
            weight -= routesTable[start][adj]
else:
    return "No such route exists"


return shortestRoute

graph = {'A': {'B': 5, 'D': 5, 'E': 7 },'B': {'C': 4},'C': {'D': 8, 'E': 2},'D': {'C': 8, 'E':  6},'E': {'B': 3}}

print(findShortestRoute('B', 'B', 0, 0, [], graph))

在循环加权图中查找最短路径

Finding shortest path in a cyclic weighted graph

python

graph-algorithm

path-finding