【经典算法】从原理到实战：一文吃透有向无环图中的单源最短路径问题

本文介绍了有向无环图（DAG）中的单源最短路径问题及其基于拓扑排序的解决方法。文章从地图导航等生活实例引入主题，详细阐述了DAG的概念及其在任务调度、课程安排等场景中的应用。针对单源最短路径问题，提出了基于拓扑排序的高效算法，包括拓扑排序步骤和松弛操作，并给出了Python实现代码。通过一个项目管理案例，展示了如何利用该算法计算任务的最短时间路径和项目关键路径。最后，文章总结了算法要点并推荐了进一

大雨淅淅1999

997人浏览 · 2025-08-26 14:08:24

大雨淅淅1999 · 2025-08-26 14:08:24 发布

4.3 代码实现（以 Python 为例）

一、从生活实例引入主题

想象一下，你身处一座大城市，计划从家中前往城市另一端的工作地点。打开手机地图，输入起点和终点后，地图软件迅速为你规划出了一条最佳路线。这条路线不仅考虑了道路的实际长度，还可能考虑了路况、交通信号灯等待时间等因素，确保你能以最短的时间抵达目的地。

这看似简单的导航功能，背后却隐藏着一个复杂而有趣的计算机科学问题：在有向无环图（Directed Acyclic Graph，DAG）中寻找单源最短路径。在这个城市交通的例子中，城市中的各个地点可以看作是图中的顶点（Vertex），连接这些地点的道路则是边（Edge），而道路的长度、通行时间等信息就构成了边的权重（Weight）。由于交通规则限制，某些道路可能是单向通行的，这就形成了有向图；同时，为了简化问题，我们假设不会出现从一个地点出发，经过一系列道路后又回到原点的情况，即图中不存在环，这就是有向无环图。

那么，计算机是如何在这样庞大而复杂的有向无环图中，快速准确地找到从一个源点（如你的家）到其他所有顶点（城市中的各个地点）的最短路径呢？这正是本文要探讨的核心内容 —— 有向无环图中的单源最短路径问题，接下来，我们将深入了解其原理和代码实现。

二、有向无环图（DAG）基础概念

2.1 什么是有向无环图

有向无环图（Directed Acyclic Graph，DAG），从名字就可以看出它具有两个关键特性：有向性和无环性。在数学和计算机科学领域，它是一种由顶点（Vertices）和有向边（Directed Edges）组成的图状数据结构。

顶点，也可称为节点（Nodes），是图中的基本元素，可以用来表示各种事物或对象。比如在前面提到的城市交通例子中，城市里的各个地点就是顶点；在任务调度场景中，每个任务可以看作一个顶点。

有向边则是连接两个顶点的带有方向的线段，它表示了顶点之间的一种单向关系。例如在一个表示任务依赖关系的有向无环图中，如果存在一条从顶点 A 指向顶点 B 的有向边，那就意味着任务 A 的完成是任务 B 开始的前提条件，即任务 B 依赖于任务 A 。

而无环性是有向无环图的重要特征，它保证了在图中不存在这样的路径：从某个顶点出发，沿着有向边遍历，最终又回到了这个顶点。我们可以想象一下，如果在任务调度中出现了环，就会出现任务 A 依赖任务 B，任务 B 又依赖任务 A 这种死循环的情况，这显然是不合理且无法执行的。

为了更直观地理解，我们来看一个简单的图示：

A

/ \

B C

\ /

D

在这个有向无环图中，A、B、C、D 是顶点，箭头表示有向边。从 A 出发，可以到达 B 和 C；从 B 和 C 又可以到达 D，但无论如何都无法从 D 回到 A、B 或 C，满足有向无环的特性。

2.2 有向无环图的应用场景

有向无环图在实际生活和计算机科学领域有着广泛的应用，以下是一些常见的例子：

任务调度：在一个大型项目中，往往包含许多相互依赖的任务。比如开发一款软件，可能需要先完成需求分析，然后进行设计，接着是编码，最后进行测试。这些任务之间的依赖关系就可以用有向无环图来表示，通过拓扑排序算法（后续会详细介绍），可以确定这些任务的执行顺序，从而确保项目顺利进行。

课程安排：在大学课程体系中，不同课程之间存在先修关系。例如，学习数据结构课程之前，通常需要先掌握编程语言基础和离散数学等先修课程。利用有向无环图可以清晰地描述这些课程之间的依赖关系，帮助学校合理安排课程顺序，确保学生在具备相应基础知识后再学习更高级的课程。

编译优化：在编译器中，有向无环图可用于表示程序中的数据流和控制流。编译器通过分析这些图，可以执行各种优化操作，如常量折叠（将一些在编译时就能确定结果的常量表达式直接计算出结果，而不是在运行时计算）、公共子表达式消除（去除程序中重复计算的表达式）等，从而提高程序的执行效率。

区块链技术：一些新型区块链采用有向无环图结构来提高交易处理的效率和并发能力。与传统区块链的链式结构不同，有向无环图中的每个节点可以直接引用多个其他节点，使得交易的确认和传播更加快速，并且能够支持更多的并发交易。

可以看出，有向无环图在解决各种具有依赖关系的问题上发挥着重要作用，它为我们提供了一种清晰、有效的方式来描述和处理复杂的关系结构。

三、单源最短路径问题详解

3.1 问题定义

在有向无环图的基础上，单源最短路径问题（Single-Source Shortest Paths Problem）可以定义为：给定一个有向无环图\(G=(V, E)\)，其中\(V\)是顶点集合，\(E\)是有向边集合，以及一个源点\(s \in V\)，需要找到从源点\(s\)到图中其他所有顶点\(v \in V - \{s\}\)的最短路径。这里的 “最短” 通常是指路径上所有边的权重之和最小。

例如，在一个表示城市交通网络的有向无环图中，我们指定一个源点（比如某个特定的公交站点），要计算从这个源点到其他各个公交站点的最短乘车路线，这就是一个典型的单源最短路径问题。在这个问题中，每条边的权重可能代表两个站点之间的距离、乘车时间或者乘车费用等。

3.2 与其他最短路径问题的区别

在图论中，除了单源最短路径问题，还有其他几种常见的最短路径问题，它们与单源最短路径问题既有联系又有区别：

单目的地最短路径问题（Single-Destination Shortest Paths Problem）：与单源最短路径相反，它是要找到从图中每个顶点到一个给定目的地顶点的最短路径。比如在一个物流配送场景中，所有货物都要运往同一个配送中心，就需要计算各个发货点到这个配送中心的最短路径。通过将图中所有边的方向翻转，单目的地最短路径问题就可以转化为单源最短路径问题来求解。

单节点对最短路径问题（Single-Pair Shortest Path Problem）：该问题是要找到从给定的一个起始节点到另一个给定的目标节点的最短路径。比如在地图导航中，用户指定起点和终点，系统计算这两点之间的最短路线。单源最短路径算法可以用来解决单节点对最短路径问题，只要将起始节点作为源点，计算出从源点到所有顶点的最短路径后，就可以得到从起始节点到目标节点的最短路径。

所有节点对最短路径问题（All-Pairs Shortest Paths Problem）：这个问题要求计算图中任意两个顶点之间的最短路径。例如在社交网络分析中，可能需要知道任意两个用户之间的最短 “社交距离”（通过共同好友等关系连接的最短路径）。解决所有节点对最短路径问题的经典算法是 Floyd-Warshall 算法，它的时间复杂度为\(O(V^3)\)，而如果对每个顶点都运行一次单源最短路径算法（如 Dijkstra 算法），时间复杂度为\(O(V \cdot E + V^2 \cdot logV)\)（当使用优先队列优化的 Dijkstra 算法时），对于某些稀疏图，这种方法可能比 Floyd-Warshall 算法更高效。

总的来说，单源最短路径问题是其他几种最短路径问题的基础，它专注于从一个特定源点出发到其他所有顶点的最短路径计算，而其他问题则是在不同的目标设定下，对最短路径的求解有不同的侧重点。

3.3 重要性与应用

单源最短路径问题在众多领域都有着极其重要的应用，以下是一些典型的例子：

地图导航与路径规划：这是我们日常生活中最常见的应用之一。无论是开车出行、乘坐公共交通还是步行，地图导航软件都需要根据我们输入的起点（源点），计算到各个目的地（其他顶点）的最短路径。除了考虑实际的地理距离，导航软件还会结合实时交通信息，将道路拥堵程度转化为边的权重，从而为用户提供最快的出行路线。例如，在早晚高峰时段，拥堵路段的权重会增加，导航软件会尽量避开这些路段，为用户规划更高效的路径。

通信网络：在通信网络中，数据需要从一个节点（源点）传输到其他各个节点。为了确保数据能够快速、准确地传输，需要找到从源节点到其他节点的最短路径。这里的最短路径可能是指跳数最少（经过的中间节点最少），也可能是考虑带宽、延迟等因素后的综合最优路径。例如，在一个大型的互联网数据中心内部网络中，服务器之间的数据传输就需要通过最短路径算法来优化路由，以提高数据传输效率，降低延迟。

物流配送：物流企业需要规划从配送中心（源点）到各个客户地址（其他顶点）的最优配送路线，以降低运输成本、提高配送效率。通过单源最短路径算法，可以综合考虑运输距离、交通状况、配送时间窗口等因素，为每辆配送车辆规划出最佳的行驶路线，从而实现资源的优化配置，提高物流企业的竞争力。

项目管理：在项目管理中，任务之间存在依赖关系，我们可以将任务看作顶点，任务之间的依赖关系看作有向边，边的权重可以表示任务的执行时间。通过单源最短路径算法，可以计算从项目启动任务（源点）到其他各个任务的最短时间路径，从而确定项目的关键路径和最短完成时间，帮助项目管理者合理安排资源、监控项目进度，确保项目按时完成。

可以看出，单源最短路径问题在现代社会的各个方面都发挥着关键作用，它为我们解决各种实际问题提供了有效的数学模型和算法支持，帮助我们做出更优化的决策。

四、解决算法：基于拓扑排序的方法

4.1 拓扑排序

拓扑排序（Topological Sorting）是对有向无环图（DAG）的顶点进行排序的一种方法，它可以生成一个线性序列，使得对于图中的任意一条有向边(u, v)，顶点u在排序序列中都位于顶点v之前。简单来说，拓扑排序可以帮助我们确定具有依赖关系的任务或元素的执行顺序。

例如，在大学课程学习中，课程之间存在先修关系。假设课程 A 是课程 B 的先修课程，那么在拓扑排序后的课程学习顺序中，课程 A 必然排在课程 B 之前。这就确保了学生在学习课程 B 之前，已经掌握了课程 A 的知识，符合课程学习的逻辑顺序。

在实现上，我们可以使用深度优先搜索（DFS）来实现拓扑排序，具体步骤如下：

从图中任意选择一个未访问过的顶点开始，进行深度优先搜索。
在访问一个顶点时，将其标记为已访问。
递归地访问该顶点的所有未访问过的邻接顶点。
当一个顶点的所有邻接顶点都被访问过后，将该顶点添加到一个栈中。
重复步骤 1 - 4，直到所有顶点都被访问。
最后，将栈中的顶点依次弹出，得到的序列就是拓扑排序的结果。

下面我们通过一个具体的有向无环图实例来展示拓扑排序的过程：

A

/ \

B C

\ /

D

从顶点 A 开始进行 DFS，访问 A 后标记 A 为已访问，然后递归访问 A 的邻接顶点 B 和 C。
访问 B 后标记 B 为已访问，B 的邻接顶点只有 D，递归访问 D，标记 D 为已访问。此时 B 的所有邻接顶点都被访问，将 B 压入栈中。
回到 A，访问 C，标记 C 为已访问，C 的邻接顶点也只有 D，D 已被访问，此时 C 的所有邻接顶点都被访问，将 C 压入栈中。
回到 A，A 的所有邻接顶点都被访问，将 A 压入栈中。
最后栈中元素从栈顶到栈底依次为 A、C、B、D，这就是该图的一个拓扑排序结果。当然，由于在选择起始顶点和访问邻接顶点时存在多种选择，所以拓扑排序的结果可能不唯一，但都满足有向边的先后顺序。

4.2 算法步骤

基于拓扑排序来解决有向无环图的单源最短路径问题，主要步骤如下：

初始化距离：创建一个距离数组distances，用于存储从源点到各个顶点的最短距离。将所有顶点的距离初始化为无穷大（在 Python 中可以用float('inf')表示），表示当前还不知道从源点到这些顶点的最短路径。然后将源点到自身的距离设为 0，因为源点到自身的距离显然为 0 。
拓扑排序：对有向无环图进行拓扑排序，得到一个拓扑序列。这个序列保证了对于图中的任意一条有向边(u, v)，顶点u在序列中一定位于顶点v之前。这是后续能够正确计算最短路径的关键，因为它确保了在计算某个顶点的最短路径时，其所有前驱顶点的最短路径已经被计算出来。
松弛操作：按照拓扑排序得到的序列，依次处理每个顶点。对于当前处理的顶点u，遍历它的所有邻接顶点v。如果通过顶点u到达顶点v的距离（即distances[u] + weight(u, v)，其中weight(u, v)表示边(u, v)的权重）小于当前记录的distances[v]，则更新distances[v]为distances[u] + weight(u, v)。这个过程称为松弛操作，它不断尝试寻找更短的路径，逐步更新从源点到各个顶点的最短距离。

4.3 代码实现（以 Python 为例）

from collections import defaultdict

# 定义图类

class Graph:

def __init__(self, vertices):

self.graph = defaultdict(list) # 使用defaultdict创建图的邻接表，方便添加边

self.V = vertices # 顶点数

# 添加边的方法

def add_edge(self, u, v, w):

self.graph[u].append((v, w)) # 将边 (u, v) 及其权重 w 添加到邻接表中

# 拓扑排序的辅助函数，使用DFS

def topological_sort_util(v, visited, stack, graph):

visited[v] = True # 标记当前顶点为已访问

for i, _ in graph[v]: # 遍历当前顶点的所有邻接顶点

if not visited[i]:

topological_sort_util(i, visited, stack, graph) # 递归访问未访问过的邻接顶点

stack.insert(0, v) # 将当前顶点插入栈的开头

# 执行拓扑排序

def topological_sort(graph, V):

visited = [False] * V # 初始化所有顶点为未访问

stack = [] # 用于存储拓扑排序结果的栈

for i in range(V): # 对每个顶点进行DFS

if not visited[i]:

topological_sort_util(i, visited, stack, graph)

return stack # 返回拓扑排序后的栈，即拓扑序列

# 计算单源最短路径

def shortest_path(graph, s, V):

dist = [float('inf')] * V # 初始化所有顶点的距离为无穷大

dist[s] = 0 # 源点到自身的距离为0

top_order = topological_sort(graph, V) # 进行拓扑排序

for i in top_order: # 按照拓扑序列依次处理每个顶点

for j, weight in graph[i]: # 遍历当前顶点的所有邻接顶点及其权重

if dist[i] != float('inf') and dist[i] + weight < dist[j]:

dist[j] = dist[i] + weight # 进行松弛操作，更新最短距离

return dist # 返回从源点到所有顶点的最短距离列表

# 示例

g = Graph(6)

g.add_edge(0, 1, 10)

g.add_edge(0, 2, 3)

g.add_edge(1, 3, 1)

g.add_edge(1, 2, 4)

g.add_edge(2, 1, 2)

g.add_edge(2, 3, 8)

g.add_edge(2, 4, 2)

g.add_edge(3, 4, 7)

g.add_edge(3, 5, 9)

g.add_edge(4, 5, 4)

source = 0

distances = shortest_path(g.graph, source, g.V)

print("从源点", source, "到其他顶点的最短距离为：")

for i in range(g.V):

print("到顶点", i, "的距离：", distances[i])

4.4 复杂度分析

时间复杂度：

- 拓扑排序部分：使用深度优先搜索实现拓扑排序，每个顶点和每条边都会被访问一次，所以时间复杂度为\(O(V + E)\)，其中V是顶点数，E是边数。

- 最短路径计算部分：在计算最短路径时，按照拓扑序列依次处理每个顶点及其邻接顶点，同样每个顶点和每条边都会被访问一次，时间复杂度也是\(O(V + E)\)。

- 总体时间复杂度：由于这两个步骤是顺序执行的，所以基于拓扑排序的单源最短路径算法的总时间复杂度为\(O(V + E)\) 。

空间复杂度：

- 存储图的邻接表：需要\(O(V + E)\)的空间来存储图的邻接表，因为每个顶点需要存储其邻接顶点的信息，每条边会在邻接表中出现一次。

- 辅助空间：在拓扑排序过程中，需要使用一个栈来存储拓扑序列，以及一些辅助数组（如访问标记数组），这些辅助空间的大小都与顶点数V相关，所以辅助空间复杂度为\(O(V)\) 。

- 总体空间复杂度：综合考虑，该算法的空间复杂度为\(O(V + E)\) 。

可以看出，基于拓扑排序的方法在解决有向无环图的单源最短路径问题时，具有较低的时间复杂度和空间复杂度，是一种非常高效的算法，尤其适用于处理大规模的有向无环图。

五、实际案例分析

5.1 案例背景

假设你正在负责一个软件开发项目，该项目包含多个任务，任务之间存在依赖关系，并且每个任务都有预计的完成时间。我们可以将这个项目的任务结构看作一个有向无环图，其中每个任务是图中的顶点，任务之间的依赖关系是有向边，边的权重则是任务的完成时间。

具体任务及依赖关系如下：

任务 A（需求分析）：完成时间为 3 天，无前置任务。

任务 B（设计）：完成时间为 5 天，依赖任务 A。

任务 C（前端开发）：完成时间为 7 天，依赖任务 B。

任务 D（后端开发）：完成时间为 6 天，依赖任务 B。

任务 E（数据库搭建）：完成时间为 4 天，依赖任务 A。

任务 F（集成测试）：完成时间为 3 天，依赖任务 C、D 和 E。

任务 G（部署上线）：完成时间为 1 天，依赖任务 F。

用有向无环图表示如下：

A(3)

/ \

B(5) E(4)

/ \

C(7) D(6)

\ | /

F(3)

\

G(1)

在这个图中，我们将任务 A 作为源点，希望计算从任务 A 开始到其他各个任务的最短时间路径，以确定整个项目的最短完成时间以及每个任务的最早开始时间。

5.2 问题求解

初始化距离：

- 创建一个距离数组distances，长度为任务数量（这里是 7 个任务，索引从 0 到 6，分别对应任务 A 到任务 G），并将所有元素初始化为无穷大float('inf')。

- 将源点任务 A（索引为 0）到自身的距离设为 0，即distances[0] = 0。

拓扑排序：

- 使用深度优先搜索（DFS）对有向无环图进行拓扑排序。从任务 A 开始，A 没有前驱任务，所以 A 首先被访问，标记为已访问，然后将其邻接任务 B 和 E 加入递归访问。

- 访问任务 B，B 依赖 A，A 已访问，B 标记为已访问，B 的邻接任务 C 和 D 加入递归访问。

- 依次类推，最终得到拓扑排序结果为：[A, B, E, C, D, F, G]。

松弛操作：

- 按照拓扑排序结果依次处理每个任务。

- 处理任务 A 时，其邻接任务 B 和 E，计算通过 A 到达 B 的距离为distances[A] + weight(A, B) = 0 + 3 = 3，小于distances[B]（初始为无穷大），更新distances[B] = 3；同理更新distances[E] = 3。

- 处理任务 B 时，其邻接任务 C 和 D，计算通过 B 到达 C 的距离为distances[B] + weight(B, C) = 3 + 5 = 8，小于distances[C]（初始为无穷大），更新distances[C] = 8；计算通过 B 到达 D 的距离为distances[B] + weight(B, D) = 3 + 5 = 8，小于distances[D]（初始为无穷大），更新distances[D] = 8。

- 处理任务 E 时，没有新的更短路径产生。

- 处理任务 C 时，没有新的更短路径产生。

- 处理任务 D 时，没有新的更短路径产生。

- 处理任务 F 时，其前驱任务 C、D 和 E，计算通过 C 到达 F 的距离为distances[C] + weight(C, F) = 8 + 7 = 15，通过 D 到达 F 的距离为distances[D] + weight(D, F) = 8 + 6 = 14，通过 E 到达 F 的距离为distances[E] + weight(E, F) = 3 + 4 = 7，取最小值 7 更新distances[F] = 7。

- 处理任务 G 时，计算通过 F 到达 G 的距离为distances[F] + weight(F, G) = 7 + 3 = 10，更新distances[G] = 10。

最终得到从任务 A 到其他任务的最短时间路径如下：

任务 A 到任务 A：0 天

任务 A 到任务 B：3 天

任务 A 到任务 C：8 天

任务 A 到任务 D：8 天

任务 A 到任务 E：3 天

任务 A 到任务 F：7 天

任务 A 到任务 G：10 天

5.3 结果解读

通过计算得到的最短时间路径，我们可以得出以下结论：

项目最短完成时间：从源点任务 A 到最后一个任务 G 的最短时间为 10 天，这就是整个项目的最短完成时间。这意味着在理想情况下，按照合理的任务执行顺序，项目可以在 10 天内完成。

任务最早开始时间：每个任务的最短路径距离就是其最早可以开始的时间。例如，任务 B 最早可以在第 3 天开始，因为它依赖的任务 A 需要 3 天完成；任务 C 最早可以在第 8 天开始，因为它依赖的任务 B 需要在第 3 天开始并花费 5 天完成，总共 8 天。

优化项目流程：通过分析这些最短路径，我们可以清晰地看到哪些任务是关键路径上的任务（即这些任务的延迟会直接导致整个项目完成时间的延迟）。在这个例子中，任务 A、B、E、F、G 构成了关键路径。对于关键路径上的任务，我们需要重点关注，合理分配资源，确保其按时完成，以避免项目延期。而对于非关键路径上的任务（如任务 C 和 D），它们有一定的时间弹性，可以在不影响项目整体进度的前提下，适当调整资源分配或开始时间，例如可以将部分资源从非关键任务调配到关键任务上，以加快整个项目的进度。同时，也可以利用这些任务的时间弹性，更好地协调团队成员的工作安排，提高资源利用效率，从而节省时间成本和人力成本。

六、总结与展望

6.1 总结要点

在本文中，我们深入探讨了有向无环图中的单源最短路径问题。从生活中的地图导航实例出发，引出了有向无环图和单源最短路径问题的概念。有向无环图作为一种重要的数据结构，其有向性和无环性使其在描述任务依赖、课程安排等具有依赖关系的场景中发挥着关键作用。单源最短路径问题则聚焦于从一个特定源点到图中其他所有顶点的最短路径计算，在地图导航、通信网络、物流配送等领域有着广泛的应用。

我们着重介绍了解决该问题的基于拓扑排序的方法。拓扑排序通过对有向无环图的顶点进行排序，生成一个满足有向边先后顺序的线性序列，为计算最短路径奠定了基础。基于拓扑排序的单源最短路径算法，首先对图进行拓扑排序，然后按照拓扑序列依次对每个顶点进行松弛操作，不断更新从源点到其他顶点的最短距离。通过 Python 代码实现，我们直观地展示了该算法的执行过程，并且分析得出其时间复杂度和空间复杂度均为\(O(V + E)\)，这使得该算法在处理大规模有向无环图时具有较高的效率。

在实际案例分析中，我们以软件开发项目任务调度为例，将任务及其依赖关系构建为有向无环图，运用基于拓扑排序的最短路径算法，成功计算出从源任务到其他任务的最短时间路径，从而确定了项目的最短完成时间和每个任务的最早开始时间，为项目管理提供了有力的决策支持。

6.2 进一步学习方向

对于希望深入学习图论和算法知识的读者，推荐阅读经典的算法书籍，如《算法导论》。这本书涵盖了丰富的算法知识，对图论相关算法有着深入的讲解和分析，能够帮助读者从理论层面深入理解算法的原理和证明，提升算法思维能力。另一本《算法（第 4 版）》则更加注重实践，书中提供了大量基于 Java 实现的代码示例，通过实际编程案例帮助读者更好地掌握算法的实现技巧和应用方法，适合希望通过实践加深对算法理解的读者。

在线课程也是学习算法的优质资源，比如麻省理工学院提供的免费公开课程 “Introduction to Algorithms”，由《算法导论》的作者亲自授课，课程内容深入全面，通过视频讲解、作业练习等多种形式，帮助学习者系统地学习算法知识。在国内，也有许多知名高校和在线教育平台提供的图论与算法课程，这些课程结合了国内的教学特点和实际案例，更便于国内读者学习和理解。

除了本文介绍的基于拓扑排序的方法，图论中还有许多其他经典的最短路径算法值得探索。例如，Dijkstra 算法适用于边权非负的有向图或无向图，它通过贪心策略不断选择距离源点最近的顶点加入集合，并更新集合外其他顶点到源点的距离，时间复杂度在朴素实现下为\(O(n^2)\)，使用优先队列优化后可达\(O((n + E)logn)\)；Bellman - Ford 算法则可以处理带有负权边的图（只要不存在负权环），通过对每条边进行多次松弛操作来找到最短路径，时间复杂度为\(O(VE)\) 。深入学习这些算法，能够让我们在面对不同类型的图和实际问题时，选择最合适的算法来高效地解决问题，进一步提升我们在算法领域的知识和技能水平。

长沙城市开发者社区

惟楚有才，于斯为盛。欢迎来到长沙！！！茶颜悦色、臭豆腐、CSDN和你一个都不能少~

更多推荐

2025 科技前沿全景：从量子突破到星际凝望的文明跃迁

长沙城市开发者社区

Maple Mono多语言支持：简繁中日字符集兼容

在当今全球化开发环境中，开发者经常需要处理包含简体中文、繁体中文、日文和英文的混合代码。传统等宽字体往往无法完美支持这种多语言场景，导致：- 中英文字符宽度比例失调，表格对齐困难- 标点符号显示不一致，影响代码可读性- 特殊符号和连字功能在多语言环境下失效- 终端图标与中文字符兼容性问题Maple Mono字体通过创新的技术方案，彻底解决了这些痛点，为多语言开发者提供了完美的字体...

长沙城市开发者社区

Graphite直方图分析：图形色彩分布的视觉化工具

还在为图像色彩分布不均衡而烦恼？想要精确掌握图像中的色彩构成却无从下手？Graphite的直方图分析功能为你提供了一套完整的色彩分布视觉化解决方案，让你能够深入理解图像的色彩特性并进行精准的色彩调整。## 什么是直方图分析？直方图（Histogram）是数字图像处理中用于表示像素值分布的重要工具。在Graphite中，直方图分析能够：- **可视化色彩分布**：直观展示RGB各通道的像...