图论算法的成本账：先看图的形状和查询目标

图论算法的成本账：先看图的形状和查询目标

算法题里，复杂度常写成一个 O 符号；服务里还要把它换算成内存、CPU 时间和查询时限。选 Floyd-Warshall、Dijkstra 还是其他算法，取决于图是否稠密、是否有负权边、需要单源还是全源最短路，以及结果是否能预计算。

先做两项判断

邻接矩阵需要 O(V²) 空间。以int64距离矩阵为例，10,000 个顶点仅元素区就约为 800 MB，未包含切片头、运行时和其他数据。稀疏图更适合邻接表，空间通常为 O(V + E)。

Dijkstra 只适用于边权非负的单源最短路径；有负权边时可考虑 Bellman-Ford，且必须处理负权环。Floyd-Warshall 能处理负权边但不能处理可达的负权环，时间和空间均为 O(V³)、O(V²)，更适合较小的全源问题。不能因为“图很大”就一律换成 Dijkstra。

func addEdge(adj [][]Edge, from, to, weight int) error { if from < 0 || from >= len(adj) || to < 0 || to >= len(adj) { return errors.New("vertex out of range") } if weight < 0 { return errors.New("dijkstra does not support negative weights") } adj[from] = append(adj[from], Edge{To: to, Weight: weight}) return nil }

内存预算只是准入条件

执行前可用顶点数、边数和元素大小估算最低内存，并为切片增长、优先队列和运行时留余量。估算超过实例预算时，返回可诊断的“图规模超限”错误，或将任务转到离线计算；不要静默截断成局部图并把结果当作精确路径。

若节点 ID 稀疏，先离散化或使用映射，不要直接把大 ID 当数组下标。对于不连通图，要明确用无穷大或(distance, reachable)表示不可达，避免在加法中溢出。

该测什么

基准输入至少分为稠密/稀疏、有/无负权、连通/不连通，并记录顶点数、边数、权重范围、机器配置和算法实现。测量峰值堆内存、分配次数、耗时和取消后的资源释放。这样得到的结果才能支持选型，而不是用一张没有条件的“性能对比表”替代判断。