Все узлы кратчайшие пути

Question

Я новый пользователь Python. Следующий код работает для поиска кратчайшего пути от исходного узла, скажем B ко всем другим узлам. Мне интересно найти кратчайшее расстояние от каждого узла.i.e, от A до всех, от B до всех, ..... от G до всех. Может ли какой-то орган помочь мне, пожалуйста, как это сделать. Спасибо.

nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G') 

distances = { 

    'B': {'A': 5, 'D': 1, 'G': 2}, 

    'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5}, 

    'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3}, 

    'G': {'B': 2, 'D': 1, 'C': 2}, 

    'C': {'G': 2, 'E': 1, 'F': 16}, 

    'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2}, 

    'F': {'A': 5, 'E': 2, 'C': 16}} 

unvisited = {node: None for node in nodes} 

visited = {} 

current = 'B' 

currentDistance = 0 

unvisited[current] = currentDistance 


while True: 

    for neighbour, distance in distances[current].items(): 

     if neighbour not in unvisited: continue 

     newDistance = currentDistance + distance 

     if unvisited[neighbour] is None or unvisited[neighbour] > newDistance: 

      unvisited[neighbour] = newDistance 

    visited[current] = currentDistance 

    del unvisited[current] 

    if not unvisited: break 

    candidates = [node for node in unvisited.items() if node[1]] 

    current, currentDistance = sorted(candidates, key = lambda x: x[1])[0] 


print(visited) 

Answer 1

Если вы пытаетесь перебрать все узлы, вы можете сделать петлю над начальным значением current. Это потребует минимальных изменений в код:

nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G') 
distances = { 
    'B': {'A': 5, 'D': 1, 'G': 2}, 
    'A': {'B': 5, 'D': 3, 'E': 12, 'F' :5}, 
    'D': {'B': 1, 'G': 1, 'E': 1, 'A': 3}, 
    'G': {'B': 2, 'D': 1, 'C': 2}, 
    'C': {'G': 2, 'E': 1, 'F': 16}, 
    'E': {'A': 12, 'D': 1, 'C': 1, 'F': 2}, 
    'F': {'A': 5, 'E': 2, 'C': 16}} 

for start in nodes: 
    current = start 
    currentDistance = 0 
    unvisited = {node: None for node in nodes} 
    visited = {} 
    unvisited[current] = currentDistance 

    while True: 
     for neighbour, distance in distances[current].items(): 
      if neighbour not in unvisited: continue 
      newDistance = currentDistance + distance 
      if unvisited[neighbour] is None or unvisited[neighbour] > newDistance: 
       unvisited[neighbour] = newDistance 
     visited[current] = currentDistance 
     del unvisited[current] 
     if not unvisited: break 
     candidates = [node for node in unvisited.items() if node[1]] 
     current, currentDistance = sorted(candidates, key = lambda x: x[1])[0] 

    print('-- Shortest distances from %s --' % start) 
    print(visited) 

В принципе, я сделал петлю над start и установить начальную current в start. Я также добавил распечатку в конце, чтобы сообщить вам, в каком начальном узле отображается информация.