爱豆文档 - 信息安全文档下载平台 - idocdown.com （部分文档，免费下载）

. . . . . .

Bellman-Ford算法检测负权环

**Bellman-Ford算法检测负权环** **题目描述** 给定一个带权有向图，其中边的权重可以是正数、负数或零。要求设计一个算法，不仅能计算从单个源点到所有其他顶点的最短路径，还能检测图中是否存在从源点可达的负权环（即总权重为负的环路）。如果存在这样的环，算法应正确报告；否则，输出最短路径长度。 **核心思路** Bellman-Ford算法通过松弛操作（Relaxation）逐步逼近最短路径。若图中不存在负权环，最多经过\(V-1\)轮松弛可得到最短路径；若第\(V\)轮松

2025-11-01 19:38:23

xxx 最大流问题（Capacity Scaling 优化）

**xxx 最大流问题（Capacity Scaling 优化）** **题目描述** 给定一个有向图 G=(V,E)，其中每条边 e 有一个非负容量 c(e)≥0。图中有一个源点 s 和一个汇点 t。最大流问题的目标是找到从 s 到 t 的最大流量，即允许通过边的流不超过其容量的情况下，从 s 发送到 t 的最大流值。Capacity Scaling 优化是 Ford-Fulkerson 方法的一种改进，通过逐步处理不同数量级的容量来提高效率，特别适用于容量差异较大的图。 **解题过程

2025-11-01 17:32:02

Hopcroft-Karp算法求二分图最大匹配

**Hopcroft-Karp算法求二分图最大匹配** **题目描述** 给定一个二分图G=(U,V,E)，其中U和V是两个不相交的顶点集合，E是连接U和V的边集合。求该二分图的最大匹配，即找到尽可能多的边，使得这些边没有公共顶点。 **算法思路** Hopcroft-Karp算法通过BFS构建层次图，然后使用DFS寻找增广路径。关键思想是每次寻找一束最短的增广路径，而不是单条路径。 **详细步骤** **1. 初始化** - 定义距离数组dist，记录U集合顶点到虚拟起点的距离 - 定

2025-11-01 14:10:53

图论中的广度优先搜索（BFS）算法

**图论中的广度优先搜索（BFS）算法** **题目描述** 广度优先搜索（BFS）是一种用于遍历或搜索图或树结构的算法。它从选定的起始顶点开始，逐层访问所有相邻顶点，再依次访问这些相邻顶点的未访问邻居，确保先访问距离起点最近的顶点。BFS常用于求解无权图的最短路径问题、连通性检测、层级遍历等。 **解题过程** 1. **初始化** - 创建一个队列（用于存储待访问的顶点）和一个集合（用于记录已访问的顶点）。 - 将起始顶点加入队列，并标记为已访问。 2.

2025-11-01 11:58:15

图论中的最短路径快速算法（SPFA）

**图论中的最短路径快速算法（SPFA）** **题目描述** 最短路径快速算法（Shortest Path Faster Algorithm，SPFA）是解决带权有向图（或无向图）中单源最短路径问题的一种算法。它是Bellman-Ford算法的一种优化版本，通过使用队列来避免不必要的松弛操作，从而在许多情况下（尤其是稀疏图）获得更好的平均时间复杂度。该算法能够处理带有负权边的图，但如果图中存在从源点可达的负权环，算法会检测到这一情况并报告问题。 **核心概念** 1. **单源最短路径**

2025-11-01 10:54:07

Johnson算法求稀疏图中所有顶点对最短路径

**Johnson算法求稀疏图中所有顶点对最短路径** **题目描述** 给定一个可能包含负权边但不含负权环的稀疏有向图，要求找出图中所有顶点对之间的最短路径距离。稀疏图是指边数|E|远小于顶点数|V|的平方（|E| << |V|²）的图。Johnson算法能高效解决这个问题，特别适合稀疏图场景。 **算法思路** Johnson算法的核心思想是通过重新赋权（reweighting）技术，消除图中的负权边，然后对每个顶点运行一次Dijkstra算法。它包含三个关键步骤： 1. 添加虚拟顶点并

2025-11-01 10:06:20

二分图的最大匹配问题（匈牙利算法）

**二分图的最大匹配问题（匈牙利算法）** 题目描述：给定一个二分图G=(X∪Y, E)，其中X和Y是两个不相交的顶点集合，E是边集。我们需要找到该二分图的一个最大匹配。匹配是指边的集合M⊆E，其中任意两条边都不共享公共顶点。最大匹配是指包含边数最多的匹配。解题过程： 1. 基本概念理解 - 二分图：顶点可划分为两个集合X和Y，所有边都连接X和Y中的顶点 - 匹配：没有公共顶点的边集合 - 增广路径：从未匹配点出发，交替经过匹配边和非匹配边，最终到达另一个未匹配点的路径 2. 算法核

2025-11-01 09:19:12

最小生成树问题（Prim算法）

**最小生成树问题（Prim算法）** **题目描述** 给定一个连通无向图G=(V, E)，其中每条边有一个正的权重（代表距离、成本等），要求找出一个边的子集T⊆E，使得T连接所有顶点，并且这些边的总权重最小。这样的子集T构成的树称为最小生成树（MST）。 **解题思路** Prim算法是一种贪心算法，它从一个顶点开始，逐步扩展树，每次添加一条连接树内顶点和树外顶点的最小权重边，直到所有顶点都被包含在树中。 **详细步骤** 1. **初始化** - 选择一个起始

2025-11-01 08:00:18

图论中的最短路径问题（Dijkstra算法）

**图论中的最短路径问题（Dijkstra算法）** **题目描述** 给定一个带权有向图（或无向图），图中每条边的权重为非负值，求从一个源点（如顶点 \(s\)）到图中所有其他顶点的最短路径长度。 **解题过程** **1. 核心思想** Dijkstra算法通过贪心策略逐步确定离源点最近的顶点，并利用这些顶点的最短路径来更新相邻顶点的距离。算法维护一个集合 \(S\)，表示已确定最短路径的顶点，初始时 \(S\) 为空。 **2. 初始化** - 创建一个

2025-11-01 06:03:32

最小生成树问题（Reverse-Delete算法）

**最小生成树问题（Reverse-Delete算法）** **题目描述** 给定一个连通的无向图 \( G = (V, E) \)，每条边 \( e \) 有一个权重 \( w(e) \)。目标是找到图 \( G \) 的一个最小生成树（MST），即一个包含所有顶点的连通无环子图，且所有边的权重之和最小。Reverse-Delete 算法通过逐步删除边来求解 MST，其核心思想是：**按权重从大到小的顺序考虑每条边，若删除该边后图仍连通，则删除该边；否则保留**。 --- **解题过

2025-11-01 03:39:57

xxx 哈密顿路径问题（回溯算法）

**xxx 哈密顿路径问题（回溯算法）** **题目描述** 哈密顿路径问题要求在一个给定的无向图中找到一条路径，使得这条路径恰好访问图中每个顶点一次且仅一次。如果这样的路径存在，则称该图为哈密顿图。需要注意的是，哈密顿路径不要求路径的起点和终点相连（即不要求形成环），而如果路径首尾相连则称为哈密顿回路。本问题聚焦于寻找哈密顿路径（不一定成环）。 **解题过程** 哈密顿路径问题属于NP完全问题，没有已知的多项式时间解法。回溯算法通过系统性地探索所有可能的路径来寻找解，其核心思想是逐

2025-11-01 00:07:37

xxx 最小费用最大流问题（Cycle Canceling算法）

**xxx 最小费用最大流问题（Cycle Canceling算法）** **题目描述** 给定一个带权有向图G=(V,E)，其中每条边e=(u,v)有两个属性：容量c(e)≥0表示最大流量，费用w(e)表示单位流量的成本。设源点s和汇点t，求从s到t的最大流f，使得总运输成本∑(w(e)·f(e))最小。 **核心概念** 这是最小费用最大流问题，需要同时满足两个目标：流量最大化、总成本最小化。Cycle Canceling算法通过消除负费用环来优化成本。 **基础准备** 1. **残

2025-10-31 23:56:53

跳转到页