【LeetCode】大厂面试算法真题回忆（168）——最小传递延时

一、问题背景与抽象建模

在通信网络、任务调度、依赖编排等工程场景中，经常会遇到如下问题：

• 网络由若干节点构成
• 节点之间存在单向依赖关系
• 边权表示传输延时或执行成本
• 网络整体不存在环路

本题正是这一类问题的典型抽象，其数学模型为：加权有向无环图（Directed Acyclic Graph, DAG）上的单源最短路径问题。

二、问题形式化定义

• 节点集合：V = {1, 2, ..., N}
• 有向边集合：E = {(u, v, w)}
• 权重w ≥ 0，表示从u到v的消息传递延时
• 给定源节点src与目标节点dst

目标：计算从src到dst的最小路径权重和；若dst不可达，返回-1。

三、对回溯解法的工程性分析

回溯解法通过枚举所有可能路径并取最小值，逻辑正确，但存在明显工程问题：

1. 时间复杂度不可控：路径数量