CODEWITHSUNDEEP
algorithmgraphshortest-pathbellman-ford
Ori Netanel Ben-Zaken
Ori Netanel Ben-Zaken

Reputation: 377

Verify a shortest path for every vertex in a directed graph

Well I'm trying to solve a problem with a more efficient solution and I can't think about anything that would work for sure than the trivial solution, also can't find the same version of this problem in any other sources I came across to so I would love for some help.

Given:

1.A directed graph G, in which every edge has a weight (weight can be negative and G may contain negative cycles).

2.A d[v] field for every vertex.

3.A source vertex s.

How can I verify for every vertex in G if d[v] is the length of the shortest path in G from s to v?

of course I can use Bellman-Ford algorithm and compare each d[v] to the distance that Bellman-Ford gave for v.. but that is pretty naive and not efficient.

Can I do better?

Thanks in advance!

Upvotes: 1

Views: 1268

Answers (1)

SaiBot
SaiBot

Reputation: 3745

You can verify if all d[v]'s are correct by using the following property that has to hold for each node v:

The shortest path from s to v has to go via the neighbour n of v for which d[n] + the cost to get from n to v is the smallest.

So you can just perform the following pseudo code, which runs in O(E) where E is the number of edges.

forall v from G:
    if(min(d[n] + w(n, v) | forall n from incoming_neighbours(v)) != d[v]):
         //something is wrong

w(n, v) is the weight between node n and v.

However, if you find an error in your d[v]'s using this method you cannot infer which ones are incorrect. In this case, as already mentioned in the comments you will have to preform Bellman-Ford.

Upvotes: 2

Related Questions