我是图论的新手。我们从节点 (1,1) 开始，需要到达节点 (r,c) ，即可以想象一个矩形，其节点编号为 2D 笛卡尔平面，我们从左上角的节点开始搜索，需要到达右下角节点。从一个节点到另一个节点的遍历具有一定的权重，因此可以在 O(n) 中使用 BFS（Breadt First Search）解决加权图的最小成本路径吗？如果 BFS 不可能，您能否建议一些不同的算法。先谢谢了。
问问题
485 次
1 回答
2
如果你是新手，那么你绝对应该看看Dijkstra 算法，这是最知名的算法，应该做你想做的事。您可以调整 BFS 来执行此操作，但它会非常慢（并且可能与 Dijkstra 做得更多或更少）。试试看，如果有任何问题再回来
于 2012-11-02T22:52:29.270 回答