时间戳

首页 > 解决方案 > Dijkstra最短路径Python3中的打印路径

python-3.x - Dijkstra最短路径Python3中的打印路径

问题描述

我在下面的代码中遇到问题，它没有显示每个顶点的任何路径。与源的顶点和距离显示正确，但输出的路径部分为空白。我错过了什么？我很想得到一些反馈或建议，甚至回答这个噩梦。我似乎无法弄清楚是什么导致路径显示任何内容。我对 Python 还是很陌生，我真的可以使用一些帮助！

我当前代码的输出

class Graph:

    def minDistance(self, dist, queue):
        # Initialize min value and min_index as -1
        minimum = float("Inf")
        min_index = -1

        # from the dist array,pick one which
        # has min value and is till in queue
        for i in range(len(dist)):
            if dist[i] < minimum and i in queue:
                minimum = dist[i]
                min_index = i
        return min_index


    def printPath(self, parent, j):

        # Base Case : If j is source
        if parent[j] == -1:
            print()
            j,
            return
        self.printPath(parent, parent[j])
        print()
        j,


    def printSolution(self, dist, parent):
        src = 0
        print("Vertex \t\tDistance from Source\tPath")
        for i in range(1, len(dist)):
            print(("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])), end=' ')
            self.printPath(parent, i)


    def dijkstra(self, graph, src):
        row = len(graph)
        col = len(graph[0])        
        dist = [float("Inf")] * row        
        parent = [-1] * row        
        dist[src] = 0  
        queue = []
        for i in range(row):
            queue.append(i)        
        while queue:            
            u = self.minDistance(dist, queue)            
            queue.remove(u)            
            for i in range(col):                
                if graph[u][i] and i in queue:
                    if dist[u] + graph[u][i] < dist[i]:
                        dist[i] = dist[u] + graph[u][i]
                        parent[i] = u        
        self.printSolution(dist, parent)


g = Graph()

graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
     [4, 0, 8, 0, 0, 0, 0, 11, 0],
     [0, 8, 0, 7, 0, 4, 0, 0, 2],
     [0, 0, 7, 0, 9, 14, 0, 0, 0],
     [0, 0, 0, 9, 0, 10, 0, 0, 0],
     [0, 0, 4, 14, 10, 0, 2, 0, 0],
     [0, 0, 0, 0, 0, 2, 0, 1, 6],
     [8, 11, 0, 0, 0, 0, 1, 0, 7],
     [0, 0, 2, 0, 0, 0, 6, 7, 0]
     ]


g.dijkstra(graph, 0)

标签： python-3.xalgorithmpathshortest-pathdijkstra

解决方案

您的代码的基本问题是该printPath方法仅输出空白，其次，该printSolution方法不包括该printPath方法的结果。要解决这些问题： 1 重写 printPath 函数，如下所示：

def printPath(self, parent, j, l):
    # Returns a list from destination to source
    # Base case when j = source
    if parent[j] == -1:
       return l
    else:
       l.append(j)
       return self.printPath(parent, parent[j], l)

然后重写printSolution方法如下：
注意：我使用f格式结构来简化我的打印语句

def printSolution(self, dist, parent):
    src = 0
    print("Vertex \t\tDistance from Source\tPath")
    
    for i in range(1, len(dist)):
        st = f"\n{src}  --> {i}\t\t{dist[i]}\t\t\t\t\t{self.printPath(parent,i,[])[::-1]}"
        #print(("\n%d --> %d \t\t%d \t\t\t\t\t" % (src, i, dist[i])), end=' ')
        #self.printPath(parent, i)
        print (st)

推荐阅读