图算法选错后怎么复盘：按边权、稠密度和负权重重做测试

图算法选错后怎么复盘按边权、稠密度和负权重重做测试Dijkstra 只适用于非负边权存在可达负环时有限最短路本身就不存在。工程代码应在入口校验这些前提并用最小反例测试拒绝分支。根据图的性质选择算法图的条件可选算法需要说明的限制边权非负Dijkstra优先队列实现通常为O((VE) log V)有负边、无可达负环Bellman-Ford时间复杂度为O(VE)稀疏图上的工程尝试SPFA最坏情况仍可能很差不能作为稳定性能保证SPFA 的入队次数限制只能帮助发现疑似负环或控制资源不能把结果“降级为正确”。一旦检测到负环应该返回明确错误并给调用方决定是拒绝该图、定位数据问题还是采用其他业务规则。func validateNonNegative(edges []Edge) error { for _, edge : range edges { if edge.Weight 0 { return fmt.Errorf(dijkstra requires non-negative weights: %d-%d, edge.From, edge.To) } } return nil } func ShortestPath(edges []Edge, source int) ([]int64, error) { if err : validateNonNegative(edges); err ! nil { return nil, err } return dijkstra(edges, source) }把验证放进测试测试至少覆盖非负权图、单条负边、可达负环、不可达负环、断开图和溢出边权。对动态规划也一样先写状态定义、边界和转移不变量再比较实现。复盘材料应包含最小反例、修复后的测试和指标查询来源。