D算法求其余节点到C节点的最短路由

求解答111111111111111111111111111111111111111111111111111111111111111

img

img

用邻接矩阵保存图。遍历邻接头到c的距离，如果小于min则输出这条路径和min有帮助请采纳

提供参考实例【最短路径算法——Dijkstra算法——python3实现】，链接：https://blog.csdn.net/anlian523/article/details/80893372?spm=1001.2101.3001.6650.3&utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-3-80893372-blog-82111659.pc_relevant_default&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7ECTRLIST%7ERate-3-80893372-blog-82111659.pc_relevant_default&utm_relevant_index=6

经过整理调试，得到了相应的代码，过程不易，希望能够对你有帮助！

如果感觉有用的话请采纳！

INF = 99999
path_matrix = {
    'A': {'B': 1, 'C': INF, 'D': INF, 'E': INF, 'F': 3, "G": 2},
    'B': {'A': 1, "C": 1, "D": INF, "E": INF, "F": INF, "G": 2},
    'C': {'A': INF, 'B': 1, 'D': 3, 'E': INF, 'F': INF, 'G': 4},
    'D': {'A': INF, 'B': INF, 'C': 3, 'E': 3, 'F': INF, 'G': 2},
    'E': {'A': INF, 'B': INF, 'C': INF, 'D': 3, 'F': 1, 'G': 2},
    'F': {'A': 3, 'B': INF, 'C': INF, 'D': INF, 'E': 1, 'G': 5},
    'G': {'A': 2, 'B': 2, 'C': 4, 'D': 2, 'E': 2, 'F': 5}
}


def the_dijkstra(path, start_node):

    visited_node = [start_node]
    result = path[start_node]
    del path[start_node]
    other_list = list(path.keys())

    while len(other_list):
        temp_node = visited_node[-1]
        if temp_node != start_node:  # 如果不是起始点
            distance_list = []
            node_list = []
            for item in other_list:
                distance_list.append(path_matrix[temp_node][item])
                node_list.append(item)
                if result[item] > result[temp_node] + path_matrix[temp_node][item]:
                    result[item] = result[temp_node] + path_matrix[temp_node][item]

            min_dist = min(distance_list)
            the_index = distance_list.index(min_dist)
            min_node = other_list.pop(the_index)
            visited_node.append(min_node)

        else:  # 如果是起始点
            # 找到距离起点路径最短的地点
            min_key = list(result.keys())[0]
            min_path = result[min_key]
            for key, value in result.items():
                if value < min_path:
                    min_path = value
                    min_key = key

            visited_node.append(min_key)
            the_index = other_list.index(min_key)
            other_list.pop(the_index)

    print(result)


the_dijkstra(path_matrix, "C")

输出结果如下：

img