在加权有向图中寻找权重最低的路径权重的算法

Question

我有一个 G=(V,E) 有向图，它的所有边的权重都为“0”或“1”。

我在图中得到了一个名为 "A" 的顶点，对于 V 中的每个 v，我需要找到从 A 到 v 的路径的权重，它在时间 O( V+E）。我只能使用 BFS 或 DFS（虽然这可能是 BFS 问题）。

我想制作一个新图，其中边为 0 的顶点合并在一起，然后在其上运行 BFS，但这会破坏图的方向（如果图是无向或权重为 {2,1}，对于 2 的边，我将创建一个新顶点）。

如有任何帮助，我将不胜感激。

谢谢

Answer 1

本题可修改为单源最短路径.

的题

只需要将所有边的方向反转，求出每个顶点v到顶点A的最小距离即可。

可以很容易地观察到，如果在初始图中，如果我们有从某个顶点 v 到 A 的最小路径，则在更改边缘方向后，我们将具有相同的从 A 到 v 的最小路径。

这可以简单地通过 Dijkstra 或因为边只有两个值 {0 和 1} 来完成，也可以通过修改后的 BFS 来完成（首先转到距离为 0 的顶点，然后是 1 , 然后 2 等等。).

Answer 2

我觉得可以结合DFS和BFS来完成。

在未加权图的原始 BFS 中，我们有一个不变量，即未探索节点的距离与已探索节点的距离更大或相等。

在我们的 BFS 中，对于每个节点，我们首先通过所有 0 加权边进行 DFS，记下距离，并将其标记为已探索。然后我们就可以继续我们BFS中的其他节点了。

Array Seen[] = false
Empty queue Q
E' = {(a, b) | (a, b) = 0 and (a, b) is of E}

DFS(V, E', u)
    for each v is adjacent to u in E' // (u, v) has an edge weighted 0
        if Seen[v] = false
            v.dist = u.dist
            DFS(V, E', v)
    Seen[u] = true
    Enqueue(Q, u)

BFS(V, E, source)
    Enqueue(Q, source)
    source.dist = 0
    DFS(V, E', source)
    while (Q is not empty)
        u = Dequeue(Q)
        for each v is adjacent to u in E
            if Seen[v] = false
                v.dist = u.dist + 1
                Enqueue(Q, v)
        Seen[u] = true

经过运行 BFS，它可以给你所有的节点源的最短距离。如果您只想到单个节点的最短距离，只需在看到目标节点时终止即可。是的，它满足了O(V+E)时间复杂度的要求。

在加权有向图中寻找权重最低的路径权重的算法

Algorithm for finding weight of path with lowest weight in weighted directed graph

algorithm

graph

breadth-first-search