图结构解析与核心最短路算法实现
图的基本定义与拓扑分类
图（Graph）是描述对象间关联关系的数学模型，通常表示为二元组 \\(G=(V,E)\\)。其中 \\(V\\) 代表顶点集合，\\(E\\) 代表边集合。根据边的属性差异，图可划分为以下几类：
- 有向图：边为有序对 \\((u,v)\\)，表示从起点 \\(u\\) 指向终点 \\(v\\) 的单向连接。
- 无向图：边为无序对 \\(\{u,v\}\\)，等价于同时存在 \\((u,v)\\) 与 \\((v,u)\\) 两条反向有向边。
- 度（Degree）：顶点的相连边数量。对有向图进一步细分为出度（起点为该顶点的边数）与入度（终点为该顶点的边数）。
- 简单图：不包含重边（多条相同起终点的边）和自环（起点与终点重合的边）的图。实际应用中绝大多数场景默认处理简单有向图。
主流拓扑结构存储方案
假设图包含 \\(N\\) 个顶点与 \\(M\\) 条边，常见的内部表达形式如下：
邻接矩阵（Adjacency Matrix）
采用二维数组 \\(A[N][N]\\) 记录连通状态。无权图中使用布尔值标记连通性；有权图则直接存入权重，不相连位置填充无穷大标识（如整型最大值）。该方案空间复杂度固定为 \\(\\Theta(N^2)\\)，适合边数密集的稠密图，但稀疏图会造成大量内存浪费。
邻接表（Adjacency List）
为每个顶点维护独立链表，仅存储实际存在的出边。空间开销降为 \\(O(V+E)\\)。针对有权图，节点结构需扩展权重字段。底层依赖动态扩容机制，频繁申请堆内存可能引发碎片化与性能损耗。
链式前向星（Forward Star）
又称静态邻接表，通过双数组模拟指针链表，彻底规避动态分配：
\\- \\texttt{head[N]}：记录以各顶点为起点的首条边在边表中的索引。
\\- \\texttt{Edge[M]}：集中存放所有边数据，含目标顶点、权重及同一起点下一条边的索引。
遍历顶点 \\(u\\) 的所有出边时，仅需从 \\texttt{head[u]} 出发，沿 \\texttt{next} 指针链式跳转即可。该结构在竞赛与高性能场景中极为常用。
无权图遍历机制
若图内所有边代价均为 \\(1\\)，可直接借助标准图遍历协议求解最短路。
广度优先搜索（BFS）
按层扩展访问顺序。首次抵达目标节点时所经过的步数必然极短。需配合队列与已访问标记数组控制流程。
from collections import deque
def bfs_shortest(unweighted_graph, start_node, target_node, total_nodes):
queue = deque([(start_node, 0)])
visited = {start_node}
while queue:
curr, dist = queue.popleft()
if curr == target_node:
return dist
for neighbor in range(total_nodes):
if unweighted_graph[curr][neighbor] and neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1
深度优先搜索（DFS）
沿单一分支深入至死胡同后回溯。虽能枚举全部路径，但因缺乏剪枝机制且会重复探索长路径，直接用于求最短距离效率极低，此处仅作逻辑演示。
def dfs_find_min_path(graph, start, target, n):
visited = [False] * n
min_distance = float('inf')
def backtrack(cur, current_dist):
nonlocal min_distance
if current_dist >= min_distance:
return
if cur == target:
min_distance = min(min_distance, current_dist)
return
visited[cur] = True
for nxt in range(n):
if graph[cur][nxt] and not visited[nxt]:
backtrack(nxt, current_dist + 1)
visited[cur] = False
backtrack(start, 0)
return min_distance if min_distance != float('inf') else -1
基于贪心策略的单源最短路
Dijkstra 算法专为非负权有向图设计。核心思想是始终选择当前距源点"理论最近"的未确定顶点进行松弛操作，逐步收敛至真实最短距离。
松弛规则：若 \\(dist[u] + w(u,v) < dist[v]\\)，则更新 \\(dist[v]\\) 并记录前驱节点。
终止优化：当目标节点被弹出优先级队列时，其最短距离已确定为最终值，可提前中断循环。
正确性证明要点：采用反证法。假设首个距离不符的弹出节点为 \\(p\\)，则必存在更优路径穿过某中间点 \\(q\\)。由于 \\(q\\) 必然先于 \\(p\\) 满足松弛条件进入队列并弹出，\\(dist[p]\\) 早已被修正，矛盾成立。因此每次弹出的节点距离均不可再优化。
import heapq
def dijkstra_weighted(adj_list, source, destination, n_nodes):
pq = [(0, source)]
min_dist = [float('inf')] * n_nodes
min_dist[source] = 0
while pq:
d_u, u = heapq.heappop(pq)
if d_u > min_dist[u]:
continue
if u == destination:
return min_dist[u]
for v, weight in adj_list.get(u, []):
new_dist = d_u + weight
if new_dist < min_dist[v]:
min_dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return -1
时间复杂度方面，二叉堆实现下为 \\(O(M + N \\log N)\\)。斐波那契堆可逼近理论最优界，但工程常数较大。
基于动态规划的全源最短路
Floyd-Warshall 算法通过中间点迭代计算任意两点间最短路径。状态 \\(dp[i][j]\\) 表示允许使用前 \\(k\\) 个节点作为中转时的最短代价。状态转移方程为：\\(dp[i][j] = \\min(dp[i][j], dp[i][k] + dp[k][j])\\)。
空间维度可从三维压缩至二维，因 \\(k\\) 递增时原地更新不会破坏后续计算逻辑。
def floyd_warshall(initial_weights, n_vertices, start, end):
INF = float('inf')
# 初始化距离矩阵
dist_matrix = [[INF] * n_vertices for _ in range(n_vertices)]
for r in range(n_vertices):
dist_matrix[r][r] = 0
for c in range(n_vertices):
if initial_weights[r][c] != INF:
dist_matrix[r][c] = initial_weights[r][c]
# 三层循环核心：外枚举中转点，内枚举起终点
for mid in range(n_vertices):
for src in range(n_vertices):
for dst in range(n_vertices):
if dist_matrix[src][mid] + dist_matrix[mid][dst] < dist_matrix[src][dst]:
dist_matrix[src][dst] = dist_matrix[src][mid] + dist_matrix[mid][dst]
return dist_matrix[start][end] if dist_matrix[start][end] != INF else -1
引入评估函数的启发式搜索
A* 算法在 Dijkstra 基础上引入预估函数 \\(h(n)\\)，综合代价定义为 \\(f(n) = g(n) + h(n)\\)，其中 \\(g(n)\\) 为起点到当前点的实际花费，\\(h(n)\\) 为当前点到目标的估算剩余花费。搜索方向由单纯的距离最小转向"实际+预估"最小。
启发函数约束
- 可采纳性（Admissibility）：\\(h(n) \leq h^*(n)\\)（预估不超过真实剩余代价），保障最终结果严格最短。
- 一致性（Consistency）：\\(h(m) \leq w(m,n) + h(n)\\)，确保节点首次展开即为最优解，避免重复检索。
几何场景适配
网格地图常采用曼哈顿距离 \\(|x_1-x_2|+|y_1-y_2|\\) 或欧几里得距离。支持对角线移动时需调整系数防止斜走成本虚高。纯图结构中若无几何信息，通常令 \\(h(n)=0\\)，此时 A* 退化为标准 Dijkstra。
流程实现
数据结构与 Dijkstra 高度一致，唯一差异在于优先队列排序依据改为 \\(f(n)\\)。其余松弛逻辑、闭环检测与退出条件完全复用。凭借合理的 \\(h(n)\\) 设计，A* 可在 vast 状态空间中显著削减探查节点数量，大幅提升寻路响应速度。
