CSP-Dijkstra及其相关变体（UVA-11374）

CSP-迪杰斯特拉算法和变形求解最短路问题

文章结构概述

• CSP-迪杰斯特拉算法及其变体用于解决最短路径问题

  • • 知识简介

    • 题目说明

    • • 输入与输入示例
      • 输出与输出示例

    • 题目重新表述

    • 解题思路（分层Dij或枚举变体）

    • 题目代码（C++）

知识简述

迪杰斯特拉（Dijkstra）算法是一种用于解决正权边单源最短路径问题的常见方法，对于该算法有所了解的人大多并不陌生。以下将简要介绍Dij算法的具体实现流程。
1、在执行迪杰斯特拉算法时，需要维护若干关键数据结构：一个最小堆用于保存当前已更新的节点，一个dis[n]数组用于记录源点s到各个节点的最短距离，以及一个vis[n]数组用于标记各节点是否已被处理。
2、接下来进入具体的操作步骤：首先将dis[n]数组的所有元素初始化为inf（极大值），并将源点s对应的dis[s]设为0；随后将s节点加入空的小根堆，并设置vis[s]为1。
3、每次从小根堆中取出最小值节点a，并遍历该节点的所有邻接边。对于某条边（a，y）及其权重w，若发现当前dis[y]大于dis[a]+w(a,y)，则表明该节点存在更新的可能性。在迪杰斯特拉算法中，这种更新过程通常被称为松弛操作，完成该