【LeetCode】大厂面试算法真题回忆（168）——最小传递延时
一、问题背景与抽象建模
在通信网络、任务调度、依赖编排等工程场景中，经常会遇到如下问题：
- 网络由若干节点构成
- 节点之间存在单向依赖关系
- 边权表示传输延时或执行成本
- 网络整体不存在环路
本题正是这一类问题的典型抽象，其数学模型为：加权有向无环图（Directed Acyclic Graph, DAG）上的单源最短路径问题。
二、问题形式化定义
- 节点集合：
V = {1, 2, ..., N} - 有向边集合：
E = {(u, v, w)} - 权重
w ≥ 0，表示从u到v的消息传递延时 - 给定源节点
src与目标节点dst
目标：计算从src到dst的最小路径权重和；若dst不可达，返回-1。
三、对回溯解法的工程性分析
回溯解法通过枚举所有可能路径并取最小值，逻辑正确，但存在明显工程问题：
- 时间复杂度不可控：路径数量