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

Question

I am given a G=(V,E) directed graph, and all of its edges have weight of either "0" or "1".

I'm given a vertex named "A" in the graph, and for each v in V, i need to find the weight of the path from A to v which has the lowest weight in time O(V+E). I have to use only BFS or DFS (although this is probably a BFS problem).

I though about making a new graph where vertices that have an edge of 0 between them are united and then run BFS on it, but that would ruin the graph direction (this would work if the graph was undirected or the weights were {2,1} and for an edge of 2 i would create a new vertex).

I would appreciate any help.

Thanks

HenryLee HenryLee · Accepted Answer · 2016-03-26T06:30:18

I think it can be done with a combination of DFS and BFS.

In the original BFS for an unweighted graph, we have the invariant that the distance of nodes unexplored have a greater or equal distance to those nodes explored.

In our BFS, for each node we first do DFS through all 0 weighted edges, mark down the distance, and mark it as explored. Then we can continue the other nodes in our 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

After running the BFS, it can give you all shortest distance from the node source. If you only want a shortest distance to a single node, simply terminate when you see the destination node. And yes, it meets the requirement of O(V+E) time complexity.

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

2 Answers