CODEWITHSUNDEEP
algorithmshortest-pathbellman-ford
user2375340
user2375340

Reputation: 97

Shortest-path, 2 weight functions

The question goes like this: A directed graph G = (V,E) is given, two vertices s,t, and two weight functions w1, w2. There are no negative weighted cycles in G (by both w1 and w2). I need to describe an algorithm that finds the shortest-path from s to t by w2, among the given shortest-paths from s to t.

I've found this: FInding All Shortest Paths Between Two Vertices but the answers seem pretty vauge to me.

I have no idea how to solve this (even a lame one). any help would be appreciated.

Upvotes: 0

Views: 1346

Answers (1)

amit
amit

Reputation: 178451

The idea is to make w2 important - but not enough to affect thew outcome of w1.

Let SUM2 be the sum of w2 on all edges: SUM2 = Sum { w2(e) | e in E }, and min{w1} = min { w1(e) | e in E } (minimal value according to w1)

Based on this, create your new weight function:

w(e) = w1(e) + w2(e)/min{w1}*(SUM2+1)

Now, given all shortest paths according to w1 - it is obvious why shortest paths according to w2 will be favored among them.

On the other hand, w2 is not 'strong' enough to overcome the importance of w1 and dominate, since note that the combined sum of ALL edges according to w2 is now less than a single node in w1

Use the above w with any shortest path algorithm to get your desired shortest path.

Upvotes: 1

Related Questions