Question

Problem 5. (Lexicographical Optimisation with Paths) Provide pseudocode and an expla- nation for an algorithm that computes a path between two nodes in an undirected graph such that: . The maximum weight in the path is minimised, ie., there does not exist another path with a smaller maximum weight .Amongst all such paths, it finds the path with minimum cost. . The time complexity is no worse than 0(( and V is the set of nodes. ·IvD-log(IVD), where E is the set of edges In mathematical arguments an oracle refers to some black box mechanism which provides some value. In this case the value is the pivot. It usually corresponds to convenient assumption for the sake of the proof, in this case the assuumption is that we can always select a pivot in the middle half of values in the array. 6 For example, consider computing the optimunn path between nodes t 0 and t ร for the following graph: 3 0 5 3 The optimum solution according to the above criteria is the path p (), V2,v3, vs). The path pe is considered more favourable than the path p (o,i,vA,s) as the minimum maximum weight of pe is 2 compared to 3 for P, even though cost(p-65-cost(p) Your algorithm should take the following input/produce the following output: Input: An weighted undirected graph G, a start node vs, an end node ve Output: The path between v and ve which satisfies the above conditions, and the total cost.

Answer 1

Here, we can use an approach similar to Djikstra's. But we have to apply a check for minimum "MAXIMUM WEIGHT" for the array.

function ModifiedDjikstra(Graph,sourceVertex):

for each vertex vert in Graph:

costOfGraph[vert] := -infinity ; //First we Define Unknown cost from every vertex to every //other vertex

previousOfVertex[vert] := undefined ; //And we define all previous vertex as undefined for every //vertex

end for

costOfGraph[sourceVertex] := infinity ; //This is cost from source to source

A := the set of each and every node in the Graph ;

while A is not Empty:-

b:= vertex in A with largest width in costOfGraph[]

remove b from A //as this has largest cost

if(costOfGraph[b] is -infinity) // This means we are still at initial state

break;

end if

for each neighbour c of b //c has not been removed from A

alternate := min(costOfGraph[c], max(costOfGraph[b], cost_between(b, c))) ; //we define //alternate as the cost with minimum maximum cost.It is minimum of cost of c and maximum of cost of b and between costs //of path

if(alternate<costOfGraph[c]) //Now we replace alternate if it is less than cost of c

costOfGraph[c]=alternate //we post cost of c as alternate as it is minimum

previousVertex[c]=b // and we set b as previous of c that gives us path

decrease-key in c in A // we then decrease key of c in array A(of all vertex)

end if

end for

end while

return width

end function

In Case of Any Queries, Please revert back