dijkstra算法无向图

### Dijkstra算法在无向图中的应用

#### 算法概述
Dijkstra算法用于计算加权图中单源最短路径问题。对于无向图而言，此算法同样适用并能有效地找出从起始节点到其他所有节点的最短路径[^1]。

#### 数据结构说明
为了实现这一目标，在程序设计过程中通常会涉及到以下几个重要变量：

- `dis[]` 数组存储各顶点至起点当前已知的最短距离；
- `flag[]` 或者称为 `visited[]` 布尔数组记录各个顶点是否已经被访问过；
- `prev[]` 记录每个顶点前驱的信息以便后续构建具体路径[^3]。

#### 实现过程
下面给出Python版本的具体代码示例来展示如何利用上述数据结构完成Dijkstra算法针对无向图的操作：

import heapq

def dijkstra(graph, start):
    n = len(graph)
    dis = [float('inf')] * n  # 初始化距离列表，默认无穷大
    prev = [-1] * n          # 存储上一跳节点信息
    visited = [False] * n     # 是否已经处理过的标志位
    
    pq = [(0, start)]        # 使用优先队列保存待处理节点及其临时距离
    dis[start] = 0           # 起点到自身的距离设为零

    while pq:
        (dist, u) = heapq.heappop(pq)

        if not visited[u]:
            visited[u] = True
            
            for v, weight in graph[u].items():
                alt = dist + weight
                
                if alt < dis[v]:
                    dis[v] = alt
                    prev[v] = u
                    heapq.heappush(pq, (alt, v))
                    
    return dis, prev         # 返回最终得到的距离表以及路径重建所需的数据

在这个例子中，输入参数是一个字典形式表示的邻接矩阵graph，其中键代表节点编号而值则是另一个字典，描述了相邻节点及其边权重；start指定了出发位置。函数返回的是两个列表：一个是到达每一个终点所需的最小代价(dis)，另一个是用来追踪最佳路线(prev)[^2]。