python实现的迪杰斯特拉算法

Python实现的迪杰斯特拉算法可以参考以下代码示例：

def Dijkstra(network, s, d):
    # 创建一个空的路径列表和距离字典
    path = []
    dist = {}
    # 初始化距离字典，起点到所有节点的距离为无穷大
    for node in network:
        dist[node] = float('inf')
    dist[s] = 0 # 起点到起点的距离为0

    while dist:
        # 选取距离最小的节点作为当前节点
        curr_node = min(dist, key=dist.get)
        # 如果当前节点是终点，则代表找到了最短路径，结束循环
        if curr_node == d:
            break
        # 移除当前节点
        del dist[curr_node]
        # 遍历当前节点的所有邻居节点
        for neighbor in network[curr_node]:
            # 计算从起点经过当前节点到邻居节点的距离
            new_dist = dist[curr_node] + network[curr_node][neighbor]
            # 如果新距离小于邻居节点当前的距离，则更新邻居节点的距离
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                # 更新邻居节点的路径为经过当前节点
                path[neighbor] = curr_node

    # 根据路径字典构建最短路径
    shortest_path = [d]
    while d != s:
        d = path[d]
        shortest_path.insert(0, d)

    return shortest_path, dist[d]

这个函数接受一个有向图（用邻接矩阵表示）`network`，起点`s`和终点`d`作为输入，然后返回从起点到终点的最短路径和代价。算法的主要思想是通过选取尚未确定最短路径的顶点中距离最小的顶点来扩展已确定最短路径的顶点集合，以此不断向图中的其他顶点扩展最短路径，直到扩展至终点或无法继续扩展为止。 <span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [Python实现迪杰斯特拉算法过程解析](https://download.csdn.net/download/weixin_38696090/13707098)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [Python实现迪杰斯特拉算法并生成最短路径的示例代码](https://download.csdn.net/download/weixin_38640168/14908408)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [基于Python实现迪杰斯特拉算法的最佳路径选择](https://blog.csdn.net/qq_19309473/article/details/130242728)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]