【图论】迪杰斯特拉算法
迪杰斯特拉算法是由荷兰计算机科学家艾兹赫尔・迪杰斯特拉于 1956 年提出的单源最短路径算法，用于求解带权有向、 无向图中，从一个源节点到其余所有节点的最短路径问题（要求图中所有边的权值非负）。
一、核心思想
贪心策略：每次从未确定最短路径的节点中，选择距离源节点最近的节点，将其标记为 “已确定”；
松弛操作：以该节点为中介，更新其邻接节点到源节点的距离；
重复上述步骤，直到所有节点都被标记为 “已确定”。
二、算法步骤（以无向带权图为例）
假设图有
n 个节点，源节点为 s：初始化：
距离数组
dist[]：dist[s] = 0（源节点到自身距离为 0），其余节点dist[i] = ∞（无穷大）；标记数组
visited[]：所有节点初始为false（未确定最短路径）；优先队列（小顶堆）：存储
(当前距离, 节点)，初始入队(0, s)。（朴素解法不使用优先队列）迭代求解：
取出优先队列中距离最小的节点
u，若u已访问则跳过；标记
u为已访问（visited[u] = true）；遍历
u的所有邻接节点v，若dist[v] > dist[u] + 权值(u,v)，则更新dist[v] = dist[u] + 权值(u,v)，并将(dist[v], v)入队；终止条件：优先队列为空，此时
dist[]数组存储源节点到所有节点的最短路径。（朴素解法不使用优先队列）