CODEWITHSUNDEEP
algorithmgraphcomputer-science
Elimination
Elimination

Reputation: 2723

Find lightest paths from a vertex in a linear-time

Let G(V,E), a directed graph with weighted edges (w:E -> R) and a r in V. It is known that for each u there's a lightest path (by weights) which is also a shortest path (by edges), from r to u. Describe an algorithm to find lightest paths from r to each u.

So what I thought about is simply running a BFS algorithm from r with a simple change; When we reach a vertex v, we sort all edges coming out of it and put vertices in queue by edges order (from smallest to largest).

This way we are getting a graph of shortest paths (As BFS should do) but we also prefer the lightest one from two shortest paths.

Let's assume my algorithm is correct, the problem is that it's not the most efficient one, since we have to sort all edges which summed up to O(|E|lg |E|).

How can it be done in linear time (O(|V|+|E|)?

Upvotes: 1

Views: 419

Answers (1)

Ami Tavory
Ami Tavory

Reputation: 76386

Following is the psuedocode for BFS from Introduction To Algorithms:

BFS(G,s)

    for each vertex u in V[G] - {s}
        do color[u] <-- white
            d[u] <-- infinity
            pi[u] <-- nil 
    color[s] <-- gray
    d[s] <-- 0
    pi[s] <-- nil
    Q <-- {s} 
    while Q != empty set
        do u <-- head[Q]
        for each v in Adj[u]
            do if color[v] = white
                then color[v] <-- gray
                    d[v] <-- d[u] + 1
                    pi[v] <-- u
                    EnQueue(Q,v) DeQueue(Q)
            color[u] <-- black

Your question states that

It is known that for each u there's a lightest path (by weights) which is also a shortest path (by edges), from r to u.

Note that, by definition, this is recursive.

You can, therefore, modify it as follows:

  1. Add to each node also c[u] (the cost of u), and initialize all to infinity. Also, add cp[u], the "cost parent" of u.

  2. When you encounter a node v in the adjacency of u, and v is not black, check if the cost of u + the cost of the edge is lower than the current cost of v. If so, update both the cost of v, and make its cost parent u.

Upvotes: 2

Related Questions