给定一个有向图 G 、权重、s 源顶点和图中每个顶点的 d[v]（从 s 到 v 的距离），我需要找到一种算法来构建最短路径图。
我正在考虑通过 BFS 处理边，但我怎么知道哪条边应该在树中，以及如何检查每个顶点的 d[v] 是否为真。
问问题
155 次
2 回答
3
BFS 算法可帮助您找到给定根节点和所有其他节点之间的最短路径，仅适用于未加权图（或所有权重相同）。如果每条边的权重不同，那么 Dijkstra 算法是一个不错的选择。但是，如果图中存在负权重，则 Dijkstra 算法不起作用。如果有负权重，那么你应该使用贝尔曼福特算法。
于 2012-12-23T21:13:57.703 回答
3
运行 Dijkstra。如果连接 {u,v} 的边 e 具有 d[u]+w[e]=d[v] 的属性，则该边是您正在寻找的树的一部分。
这样，您实际上可能不会得到一棵树，但任何 MST 都具有您正在寻找的属性
于 2012-12-23T20:15:39.693 回答