Dijkstra 重构图

Question

好的，所以我在 Python 中实现了 Djakstra's shortest path algorithm 并且它工作正常（距离计算正确），但我希望它成为 return 新的优化图还。这是我的作品：

nodes = ('A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I')
graph = {'A': {'B': 4, 'H': 8},
         'B': {'A': 4, 'C': 8, 'H': 11},
         'C': {'B': 8, 'D': 7, 'I': 2, 'F': 4},
         'D': {'C': 7, 'E': 9, 'F': 14},
         'E': {'D': 9, 'F': 10},
         'F': {'E': 10, 'D': 14, 'C': 4, 'G': 2},
         'G': {'F': 2, 'H': 1, 'I': 6},
         'H': {'A': 8, 'B': 11, 'I': 7, 'G': 1},
         'I': {'C': 2, 'H': 7, 'G':6}}



inf = 5000 #truncating inf as 5000
sptset = {} #shortest path tree set (SPT)
main = {} #main dict with nodes and their distances
source = 'A'

#initialization of source (starting point)
for node in nodes:
    main[node] = inf
main[source] = 0
sptset[source] = 0
temp_set = {source: 0}
path = {source: None}

current = None


while len(sptset)<len(nodes):
    path[min(temp_set, key=temp_set.get)] = current
    #keeping track of the path
    current = min(temp_set, key=temp_set.get)
    #choosing the next node to check as the minimum of the mainset 
    #(IF node IS NOT in stpset)
    sptset[current] = main.get(current)
    #adding the current node to stpset

    for neighbor in graph[current].keys():
        #for every adjacent node of the current
        alt = main.get(current) + graph[current].get(neighbor)
        #calculate the distance of current node(from the mainset) + wight to neighbor(from graph)
        if alt < main.get(neighbor):
        #if that sum is less than the distance of neighbor (from the mainset), then update it in mainset
            main[neighbor] = alt


    temp_set = {}
    for key in main.keys():
        if key not in sptset.keys():
            temp_set[key] = main.get(key)
    #this dictionary is being used to reconstruct the mainset WITHOUT the nodes already in stpset
    #(this is done so that the algorithm can be reiterated and a new current node can be chosen)


print path
print sptset

现在打印出路径后，你可以清楚地看到这只是算法路径，而不是节点的真实路径。如何根据我刚刚计算的距离找出节点的真实路径？

Answer 1

每当更新最小距离时，您都需要更新父项。因此，不要在主循环的顶部使用 path[min(temp_set, key=temp_set.get)] = current，而是在与 distance:

相同的 if 块下进行父更新

if alt < main.get(neighbor):
#if that sum is less than the distance of neighbor (from the mainset), then update it in mainset
    path[neighbor] = current
    main[neighbor] = alt

Answer 2

您不需要存储每个节点的路径：该信息已在 main 中提供。对于连接性较低的图形，可以扫描 main 以根据需要重建任何路径：

def parent_node(node):
    neighbors = graph[node]
    if len(neighbors) == 0:
        return None
    best_neighbor = min(neighbors, key=lambda neighbor: main[neighbor])
    if main[best_neighbor] >= main[node]:
        return None
    return best_neighbor

def shortest_path(node):
    path = []
    while node:
        path.append(node)
        node = parent_node(node)
    path.reverse()
    return path

farthest_node = max(graph, key=lambda node: main[node])
print shortest_path(farthest_node)

Dijkstra 重构图

Dijkstra reconstructing graph

python

dijkstra