求加权有向图中权值最低路径权值的算法

Question

给我一个图中名为“a”的顶点，对于v中的每一个v，我需要找到从a到v的路径的权重，它在时间O(v+E)中权重最低。我不得不只使用BFS或DFS（尽管这很可能是BFS的问题）。

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

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

谢谢

Answer 1

我认为可以用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