做负权图最短路径算法那段时间我正好在啃大模型应用开发顺手把两件事合并成了一个项目编号115。项目本身不算复杂把Bellman-Ford和Floyd-Warshall封装成一个带负权边检测的最短路径计算服务再通过Spring AI DeepSeek的Function Calling暴露给大模型让用户用自然语言就能查“从A到D怎么走成本最低”系统自动选算法、算结果、再组织人话回答。我挺推荐正在学AI大模型应用开发的人看看这个案子。市面上的实战课大多拿“查天气、写周报”当例子一旦切到图算法这种需要精确计算的场景很多问题就浮出来了大模型怎么把自然语言里的图结构抽成JSON工具注册后能不能扛住并发负环检测放错位置会怎么死循环。这篇我就顺着完整链路把设计和实操一步步拆开中间穿插我自己踩过的坑。1. 项目定位为什么用大模型重新包装经典图算法1.1 负权图为什么总是绕不开这两个算法最短路径问题大多数人第一反应是Dijkstra。但Dijkstra有个硬前提所有边权不能为负。一旦出现负权边贪心策略直接失效。举个例子A到B权重1B到D权重3A到C权重2C到B权重-2。Dijkstra先从A扩展B的距离置为1然后从B扩展DD的距离置为4。接着从A扩展CC的距离置为2通过C发现B可以更新到0此时B到D又能更新到3。问题是D已经被“确定”过了贪心策略不会回头重新松弛一个已经标记为确定点的节点最终答案是错的。这就是负权图最麻烦的地方一条更短的路径可能藏在后边需要反复松弛才能找出来。Bellman-Ford的思路很直白不做贪心对所有边做V-1轮松弛每轮都尝试用当前已知的最短距离去更新它的邻居。一条最短路最多经过V-1条边所以V-1轮之后必然收敛。Floyd-Warshall走的是另一个方向用动态规划枚举所有中间节点三重循环直接算全源最短路径。两个算法都能处理负权边区别在于适用场景和复杂度。我把这两个算法同时放进项目里让上层根据图的规模和查询类型自动选择。大模型不用懂算法细节它只需要知道系统里有这么一个工具支持负权边遇到负环会报错就够了。1.2 大模型在这个项目里担任的角色从一开始我就没打算让大模型去“计算”最短路径。大模型再强让它做多步图计算也容易算错而且负权图一旦算错结果没有任何参考价值。更合理的分工是大模型负责自然语言理解、参数抽取和结果解释精确计算交给封装好的算法服务。这是一个典型的Function Calling模式大模型不直接生成答案而是生成一个调用请求由外部工具执行后在把结果回传给它。这个角色划分还有一个好处算法逻辑全部在Java代码里可测试、可优化、可单测覆盖。大模型只承担“翻译官”的工作把用户那句“我想知道从仓库A到仓库D算上补贴和返现最终成本最低的路线”转成结构化的图数据和查询参数。就算模型输出有细微偏差工具侧还能做二次校验比让模型直接输出答案可靠得多。1.3 技术路线选型Spring AI DeepSeek的底层逻辑项目选型时我对比了Python的LangChain和Java的Spring AI。两边都能实现Function Calling但考虑到团队是Java主力整个算法服务用Java写最顺手直接选了Spring AI。Spring AI提供ChatClient抽象接入大模型API只需要配置一个ChatModel Bean工具注册用Tool注解它会自动把方法元信息发给大模型由模型决定何时调用这套机制很成熟。模型方面接了DeepSeek。一个很实际的原因是它是OpenAI兼容接口Spring AI里适配成本极低改一下base-url和api-key就行。还有一点DeepSeek在JSON输出和工具理解上比较稳结构化抽取很少出现字段缺失这对后续把自然语言转成图结构很关键。你可以把它理解成一个擅长“读题”的助手只要把题目描述清楚它就能把关键信息拆出来并组织成我们要的JSON格式。2. Bellman-Ford与Floyd-Warshall实现细节拆解2.1 Bellman-Ford松弛V-1轮最后再来一轮抓负环Bellman-Ford算法的核心操作叫松弛。对一条边u→v权重为w如果dist[u] w小于dist[v]就把dist[v]更新为dist[u] w。为什么是V-1轮因为在一个包含V个节点的图中任意一条最短路径都不会包含重复节点也就是说最多经过V-1条边。每一轮松弛至少能让最短路径的边数上限加1V-1轮之后所有路径都被处理完。我之前犯过一个经典错误V-1轮松弛之后直接返回结果没做负环检测。后来在一个带负环的图上测试答案居然看起来正常实际上每条路径都可以无限绕圈变短结果根本没有意义。负环检测必须单独放在V-1轮之后再对所有边做一次松弛如果还有边能被更新说明图里存在负环。这块代码我直接贴出来public MapString, Integer bellmanFord(MapString, ListEdge graph, MapString, Integer dist, String start) { int n graph.size(); // V-1 轮松弛 for (int i 1; i n; i) { boolean updated false; for (String u : graph.keySet()) { if (!dist.containsKey(u) || dist.get(u) Integer.MAX_VALUE) { continue; } for (Edge e : graph.get(u)) { if (dist.get(u) e.weight dist.get(e.to)) { dist.put(e.to, dist.get(u) e.weight); updated true; } } } if (!updated) { break; // 提前结束已经没有可更新的边 } } // 第 V 轮松弛用于检测负权环 for (String u : graph.keySet()) { if (!dist.containsKey(u) || dist.get(u) Integer.MAX_VALUE) { continue; } for (Edge e : graph.get(u)) { if (dist.get(u) e.weight dist.get(e.to)) { throw new RuntimeException(存在负权环无法计算最短路径); } } } return dist; }一个小细节松弛过程中如果某轮没有更新任何节点说明已经收敛可以提前退出没必要做满V-1轮。这个优化在稀疏图上效果很明显尤其当图本身是DAG或者正权主导时可能两三轮就结束了。2.2 Floyd-Warshall三重循环里的动态规划Floyd-Warshall的思路和Bellman-Ford完全不同。它维护一个n×n的距离矩阵dist[i][j]初始时dist[i][j]为i到j的直接边权没有边则设为无穷大dist[i][i]设为0。算法枚举每一个节点k作为中间点尝试用dist[i][k] dist[k][j]更新dist[i][j]。三重循环的顺序非常关键k必须放在最外层因为每个k代表一次“允许使用前k个节点作为中转”的阶段阶段之间是有依赖的。如果还需要还原具体路径我会用一个path矩阵记录中间点。当发现dist[i][j]能通过k更新时就把path[i][j]记为k。最后递归拼接路径即可。public void floydWarshall(int[][] dist, int[][] path, ListString nodes) { int n dist.length; for (int k 0; k n; k) { for (int i 0; i n; i) { if (dist[i][k] INF) continue; // 防止溢出 for (int j 0; j n; j) { if (dist[k][j] INF) continue; if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; path[i][j] k; } } } } // 负环检测对角线 dist[i][i] 出现负数说明存在负环 for (int i 0; i n; i) { if (dist[i][i] 0) { throw new RuntimeException(存在负权环无法计算最短路径); } } }这里有个Java编程的坑如果直接用Integer.MAX_VALUE当INF两个INF相加直接溢出成负数判断逻辑全乱。我后来统一用Integer.MAX_VALUE / 2作为无穷大或者直接用Long.MAX_VALUE / 2保证加法不会越界。2.3 算法选型对比与边界条件两个算法各有适用范围我在项目里做了一层简单适配层。如果用户查询的是“单源单终点”且边的数量不多用Bellman-Ford复杂度O(VE)更省空间。如果用户要求“算出所有节点两两之间的最短路径”或者图比较稠密用Floyd-Warshall复杂度O(V³)但是代码简单、结果全面。下面这个表是我整理算法策略时一直在用的对比参考维度Bellman-FordFloyd-Warshall解决的问题单源最短路径全源最短路径时间复杂度O(V×E)O(V³)空间复杂度O(V)O(V²)是否能处理负权边能能负环检测方式第V轮松弛是否仍更新对角线dist[i][i]0适用场景边数少、单起点查询点数少、全矩阵查询边界条件也得提前想清楚一是图不连通起点到某个节点根本没有路径dist保持INF返回结果时要把“不可达”翻译成清晰的中文提示。二是起点不在图里需要给大模型一个明确的报错信息让它重新向用户询问节点名称。三是只有一个节点的图V-1等于0Bellman-Ford直接跳过松弛要确保这种情况下dist[start]0能正常返回不会因为空边列表出错。我在前面加了一个策略路由用户只问一条路径时优先用Bellman-Ford如果问题里带“所有节点”“任意两点、所有路线”这类表述自动切到Floyd-Warshall。大模型只需要负责识别查询意图算法选择交给这层策略避免模型把复杂度算错。3. 大模型应用集成工具注册与Function Calling3.1 架构设计算法服务与大模型解耦整体链路我画得很简单用户输入自然语言 → Spring AI的ChatClient携带工具描述发送给DeepSeek → 模型返回工具调用请求 → Spring AI框架自动路由到Tool标注的方法 → 算法服务计算结果 → 结果回传给模型 → 模型组织成自然语言回复。这条链路里算法服务是一个独立的Java组件不依赖任何大模型SDK可以直接用JUnit测试也可以对外暴露REST接口供其他系统接入。解耦带来的好处是我可以先把算法部分用纯Java写透确保在100个节点的随机图、含负权边、含负环、不连通四种场景下结果全部正确再接大模型。排错的时候也能定位问题比如用户问“A到B最短路径是多少”如果返回结果不对我只需要看工具调用参数是否传对不用去怀疑Bellman-Ford本身。3.2 Spring AI的Tool注册实操Spring AI注册工具的方式非常直观我写一个GraphAlgorithmTools组件每个需要暴露给大模型的方法加Tool注解描述写清楚方法能做什么、参数含义。描述一定要详细因为大模型就是靠这段文字来判断什么时候该调用这个工具Component public class GraphAlgorithmTools { public static class ShortestPathRequest { public String start; public String end; public String graphJson; } Tool(name calculateShortestPath, description 计算有向加权图中两个节点之间的最短路径支持负权边。 graphJson的格式为{\nodes\:[\A\,\B\,\C\],\edges\:[{\from\:\A\,\to\:\B\,\weight\:2}]}。 若图中存在负权环则返回错误信息不返回路径结果。) public String calculateShortestPath(String start, String end, String graphJson) { try { Graph graph GraphParser.parse(graphJson); ShortestPathResult result ShortestPathService.compute(graph, start, end); return result.toJson(); } catch (Exception e) { return {\error\:\ e.getMessage() \}; } } }这里我特意把graphJson设计成一个String参数而不是让大模型按字段分开传。原因是大模型生成结构化参数时单个字段越多越容易出错尤其是边列表这种嵌套结构模型经常把数组长度写错。整段JSON作为一个字符串传递模型只需要保证整体合法性后端再用Jackson完整解析出错率明显下降。Spring AI拿到模型返回的工具调用请求后会自动把方法返回值作为上下文再发送给模型生成最终回复。模型会看到类似“最短路径为A→C→D总成本为-3”这样的工具输出然后把它润色成更口语化的回答。这个过程的模板代码不多Spring AI在底层把工具协议都封装好了。3.3 Prompt与入参设计让大模型正确抽图数据Prompt设计是大模型应用开发的灵魂这一块我反复调整过好几轮。核心要求是让模型严格区分“图数据”和“查询意图”。我在System Prompt里明确写了三段一是图数据的标准JSON结构包含nodes和edges数组二是查询意图的格式包括起点和终点三是特殊情况处理比如图数据缺失时要主动向用户索要遇到负环要原样返回工具报错信息。实际测试中我发现如果Prompt里没有显式说明“weight可以为负数”模型在构造JSON时偶尔会把负权边当成数据错误拒绝生成。后来我在例子中专门加了一个“补贴金额-5元”的边标注“这是正常的负权边不要修改”模型就老实了。另外一个关键点必须告诉模型“不要自己直接计算最短路径只负责抽取参数并调用calculateShortestPath工具”。如果不加这句话模型有时候会强行用自己理解回答编出一条不存在的路线。加了之后模型会优先选择工具调用。DeepSeek对这类指令遵循得不错基本一次到位。4. 完整实操从一个自然语言问题到最短路径结果4.1 业务场景带补贴的物流计费图我搭了一个物流计费场景来演示。假设有四座城市A、B、C、D边的权重代表运输成本其中部分路线有补贴所以权重为负。边数据如下{ nodes: [A, B, C, D], edges: [ {from: A, to: B, weight: 2}, {from: A, to: C, weight: 3}, {from: A, to: D, weight: 8}, {from: B, to: C, weight: 1}, {from: B, to: D, weight: 4}, {from: C, to: D, weight: -5} ] }C到D是-5表示走这条线能获得5元补贴那么A到D最便宜的路线就不是A→B→D这条成本6的路而是A→C→D总成本为3 (-5) -2。Dijkstra在这种图上是错的但Bellman-Ford能正确处理。4.2 完整调用链路与关键代码用户输入“帮我算一下从A到D算上补贴最低要花多少钱走哪条路”DeepSeek收到这句话后根据Prompt抽取图数据和查询参数返回一个工具调用意图。Spring AI框架自动触发calculateShortestPath方法。核心服务代码如下public class ShortestPathService { public static ShortestPathResult compute(Graph graph, String start, String end) { if (!graph.nodes.contains(start) || !graph.nodes.contains(end)) { throw new IllegalArgumentException(起点或终点不在图中请确认节点名称); } if (start.equals(end)) { return ShortestPathResult.of(0, List.of(start), graph); } if (graph.edges.size() 200) { return BellmanFordSolver.solve(graph, start, end); } else { return FloydSolver.solve(graph, start, end); } } }按项目规模选算法边数小于等于200走Bellman-Ford边数再多则切到Floyd-Warshall。实际返回给模型的JSON类似{ path: [A, C, D], distance: -2, negativeCycle: false, detail: A-C(3) : C-D(-5) }模型拿到这个JSON后会转化成回答“从A到D的最低成本是-2元推荐路线为A→C→D其中C到D能获得5元补贴补贴抵消后整体费用为-2元。”4.3 三个测试用例检验算法正确性我准备了三个用例覆盖最常见的边界情况。第一个是普通负权边就是上面那个物流图结果必须是A→C→D、-2。第二个是负环图比如A→B权重1B→A权重-2这时A到B理论上没有最小值Bellman-Ford必须抛出负环异常工具返回带error字段的JSON大模型转述为“图中存在负环无法计算最短路径”。第三个是不连通图比如A→B有边但C→D之间没有任何边查询C到D结果返回“节点D不可达”。这三个用例我都写成了JUnit测试。接入大模型后我用自然语言分别问三次确认模型能把工具返回的错误信息直接转述而不是自己编造解释。实测下来DeepSeek在这块的稳定性不错只要错误信息描述得足够明确它不会擅自修改结论。5. 踩坑实录与常见问题排查5.1 负环检测位置不对导致死循环我最早把负环检测放在每一轮松弛都执行本来想“提前发现负环”结果发现性能反而变差了而且某些边界情况下误报。负环的定义是经过V-1轮松弛之后如果仍存在可松弛的边说明图里有负环。所以检测必须在完整V-1轮之后再执行一轮都不能少。如果你在第二轮发现还在更新就断定有负环那只是图比较大、路径比较长还没收敛完而已。还有一种情况工具用递归方式实现Floyd路径还原时如果图里有负环会无限递归。解决方案在算法层就把负环检测放在路径还原之前命中了负环直接抛异常不让递归发生。这个坑我调试了快两个小时最后发现是路径还原和负环检测顺序反了。5.2 大模型返回的JSON不稳定Function Calling模式下工具入参的JSON由大模型生成再稳的模型也有翻车的时候。最常见的问题是节点列表重复、边的from或to指向不存在的节点、weight字段传成字符串。后来我统一在GraphParser里做了清洗和校验解析失败时返回特定错误码模型看到后会自动补充说明让用户核对。另一个技巧是尽量把graphJson的输出格式约束在工具描述里并给一个大模型可以直接参考的模板。模板越具体模型生成时就越不容易自由发挥。5.3 并发场景下工具注册状态混乱刚开始做的时候我把每次计算的中间结果存在类的成员变量里想着方便日志追踪。结果两个用户同时查询时状态互相覆盖A的路径串成了B的路径。后来我彻底改了设计所有算法函数做成无状态中间变量全部放在方法内部或者ThreadLocal里Tool方法本身只负责解析和调用不保存任何跨请求数据。这个教训很典型。大模型应用一旦上线工具调用就是并发请求任何全局可变状态都可能在极端情况下出问题。宁可多写几行传参代码也不要用成员变量做缓存。5.4 精度与边界值问题我用Integer.MAX_VALUE当无穷大结果两个INF相加直接变成负数Floyd-Warshall的松弛条件全乱了。改成Integer.MAX_VALUE / 2之后问题解决。如果你的图权重会超过10亿建议直接用Long类型避免所有精度相关的坑。还有节点编号问题。我用String表示节点A和a会被当成两个节点。用户输入“从a到d”模型可能原样传给工具工具再报错。后来我在Prompt里加了一条“节点名称统一为大写字母”工具侧也做了toUpperCase归一化这个问题才彻底消失。5.5 模型不调用工具、自己硬算还是有少数情况模型会绕开工具直接给答案。我试过在Prompt里强调“你无法直接计算最短路径必须调用工具”效果一般。最有效的方法是调低temperature到0并且在System Prompt中声明“当图中包含多条带权边时调用calculateShortestPath工具获取结果”。如果还不听话可以在业务上做一个兜底校验后端对模型输出做正则检查发现它没走工具就在回复里追加提示“结果经由算法引擎校验后再回复”。不过实测DeepSeek对工具指令理解比较到位这类情况很少发生。做完这个项目我最大感受是大模型应用开发不是让模型替代算法而是让模型成为调度员。它负责读懂用户、提取参数、解释结果而真正需要精确处理的计算必须交给底层的算法服务。只要你把工具边界描述清楚模型会表现得像个老练的接线员准确地把请求转给正确的处理单元。这套模式换任何领域都成立不一定非得是最短路径你可以在Spring AI里注册财报分析工具、库存检查工具、权限校验工具思路完全一致。