CODEWITHSUNDEEP
algorithmgraphshortest-path
JAN
JAN

Reputation: 21865

Find the shortest paths in a graph from s to all Vertices

Given the following problem :

Given the directed graph G=(V,E) with the weight function W:V→R , describe an algorithm that find the shortest paths from S to all other Vertices , where the length of the path equals to the SUM of all the vertices.You need to change an existing algorithm , to make that work , so there's no need to write a new algorithm.

Please notice that the weight function is on the Vertices and NOT(!!) on the Edges . What I was thinking is to change the Bellman-Ford algorithm and change the Relax check to the following :

1.if d[v]>d[u]+w[u]
 1.1 d[v] <<--  d[u]+w[u]
 1.2 PI[v] <<-- u

I don't think this works good enough , any idea what might be the problem ?

thanks ,Ron

Upvotes: 0

Views: 371

Answers (2)

Paul Jackson
Paul Jackson

Reputation: 2147

I think the Floyd–Warshall_algorithm is the best starting point. Of course, Wikipedia is down in protest today :).

Upvotes: 0

amit
amit

Reputation: 178451

let w:V->R be your weight function.

Create a weightening function: w':E->R as follows: w'(u,v) = w(v)

Run dijkstra/bellman-ford with w'. let d'[v] be the minimal path's weight to v, according to w'.

Then if the shortest path is s->u1->u2->...->un->v, you get: d'[v] = w'(s,u1) + w'(u1,u2) + ... + w'(un,v) [by correctness of dijkstra/bellman fofrd] and thus d'[v] = w(u1) + w(u2) + ... + w(un) + w(v) [by definition of w'].

so, at overall you get: d[v] = w(s) d'[v] and d[v] is the shortest path for vertices.

Upvotes: 2

Related Questions