CODEWITHSUNDEEP
algorithmgraph-theorybreadth-first-search
Ilan Aizelman WS
Ilan Aizelman WS

Reputation: 1630

Given undirected weighted connected graph, s,t. Find path from s to t that its most weighted edge is low as possible

Given: undirected weighted connected graph. s,t are vertices.

Question: Find an algorithm as efficient as possible that returns a path from s to t. In that path, the edge that has the highest weight, will has the least weight as possible. So if we have 5 paths from s,t and for every path we have the heaviest edge, so the minimum edge of these 5.

What I've tried:

  1. Use some algorithm to find the shortest path between s and t.
  2. Delete all the edges that are not part of the shortest paths we've found
  3. Use BFS with some modification, We run BFS depending on the number of paths from s to t. Every time we find a maximum edge and store it in an array, then we find the minimum of the array.

I'm struggling to find an algorithm that can be ran in (1), Bellman ford won't work - because it has to be directed graph. Dijkstra won't work because we don't know if it has negative circles or negative edges. And Prim is for finding MST which I'm not aware of how it can help us in finding the shortest path. Any ideas?

And other from that, If you have an algorithm in mind that can solve this question, would be much appreciated.

Upvotes: 3

Views: 983

Answers (3)

Dhruv Singh
Dhruv Singh

Reputation: 2253

  1. find the most negative edge in the graph
  2. add that (weight+1) to every edge.
  3. Now all edge are positive so you can apply Dijkstra's algorithm
  4. you can get the shortest_path between source and destination
  5. Now count the number of edges between source and destination (say x)
  6. Real shortest path will be: shortest_path - x * (weight+1)

Upvotes: 0

marvel308
marvel308

Reputation: 10458

You can solve it by converting into a MST problem, basically the path from s to t in the MST would be the path which has the least possible maximum weight

Upvotes: 1

Peter de Rivaz
Peter de Rivaz

Reputation: 33519

You can solve this with Kruskal's algorithm. Add edges as usual and stop as soon as s and t are in the same cluster.

The idea is that at each stage of the algorithm we have effectively added all edges below a certain weight threshold. Therefore, if s and t are in the same cluster then there is a route between them consisting entirely of edges with weight less than the threshold.

Upvotes: 1

Related Questions