在終端打印最短路徑

Question

我有這個python代碼來計算Dijkstra算法。我怎樣才能打印在終端（Ubuntu的）最短路徑？我嘗試了一些打印功能，但他們提出了一種不同的例外... 在此先感謝！

class Graph(object): 
""" 
A simple undirected, weighted graph 
""" 
    def __init__(self): 
     self.nodes = set() 
     self.edges = {} 
     self.distances = {} 

    def add_node(self, value): 
     self.nodes.add(value) 

    def add_edge(self, from_node, to_node, distance): 
     self._add_edge(from_node, to_node, distance) 
     self._add_edge(to_node, from_node, distance) 

    def _add_edge(self, from_node, to_node, distance): 
     self.edges.setdefault(from_node, []) 
     self.edges[from_node].append(to_node) 
     self.distances[(from_node, to_node)] = distance 


def dijkstra(graph, initial_node): 
    visited = {initial_node: 0} 
    current_node = initial_node 
    path = {} 

    nodes = set(graph.nodes) 

    while nodes: 
     min_node = None 
     for node in nodes: 
      if node in visited: 
       if min_node is None: 
        min_node = node 
       elif visited[node] < visited[min_node]: 
        min_node = node 

     if min_node is None: 
      break 

     nodes.remove(min_node) 
     cur_wt = visited[min_node] 

     for edge in graph.edges[min_node]: 
      wt = cur_wt + graph.distances[(min_node, edge)] 
      if edge not in visited or wt < visited[edge]: 
       visited[edge] = wt 
       path[edge] = min_node 

    return visited, path 

def route(graph, x, y): 
    distances, paths = dijkstra(graph, x) 
    route = [y] 

    while y != x: 
     route.append(paths[y]) 
     y = paths[y] 

    route.reverse() 
    return route 



if __name__ == '__main__': 
    g = Graph() 
    g.nodes = set(range(1, 7)) 
    g.add_edge(1, 2, 7) 
    g.add_edge(1, 3, 9) 
    g.add_edge(1, 6, 14) 
    g.add_edge(2, 3, 10) 
    g.add_edge(2, 4, 15) 
    g.add_edge(3, 4, 11) 
    g.add_edge(3, 6, 2) 
    g.add_edge(4, 5, 6) 
    g.add_edge(5, 6, 9) 
    assert route(g, 1, 5) == [1, 3, 6, 5] 
    assert route(g, 5, 1) == [5, 6, 3, 1] 
    assert route(g, 2, 5) == [2, 3, 6, 5] 
    assert route(g, 1, 4) == [1, 3, 4] 

Answer 1

可視化生成的路徑：

def print_route(graph, x, y): 
    r = route(graph, x, y) 
    prmpt = ['({})'.format(x)] 
    for y in r[1:]: 
    d = graph.distances.get((x, y)) 
    prmpt.append(' --{}-> ({})'.format(d,y)) 
    x = y 
    print(''.join(prmpt)) 

輸出節點1和5之間的最短路徑：

(1) --9-> (3) --2-> (6) --9-> (5)