trek's blog

Maximum capacity of any existing path between given two nodes.
By trek, 10 years ago, In English

problem:

Given two vertices of a graph,those are start point and end point and the weights of all edges in the graph are given.There are many paths exist from start vertex to end vertex.Find the weight of the minimum weighted edge that is present on each of those paths and find the maximum of those minimum weights.


input:
start point end point N — no. of edges
then N lines showing edges and their weights node1,node2,weight.

output:
out the maximum of those minimum weights .

note: the graph is connected and undirected.
  • Vote: I like it
  • -3
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

http://en.wikipedia.org/wiki/Widest_path_problem

Can be solved with invariants of Dijkstra's, minimum spanning tree and Floyd-Warshall algorithms as well as some other algorithms.

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually invariants of Dijkstra's is Prim's algorithm :)

    → Reply
  • »
    »
    10 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I think there is a difference between the Widest path problem and the problem from this topic. In the first case you need to find a path between two designated vertices in a weighted graph, maximizing the weight of the minimum-weight edge in the path. On the other hand, this problem asks you to find the weight of the minimum weighted edge that is present on each of those paths (there are many paths from start vertex to end vertex). Thus, you are asked to find the minimum weight of the edges whose removal will disconnect the start point and the end point.

    → Reply
    • »
      »
      »
      10 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      and find the maximum of those minimum weights.

      Looks like author meant for each of the paths instead of what he said.

      P.S. It also looks like in your interpretation we can solve problem faster and easier.

      → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +13 Vote: I do not like it

You can sort edges by decreasing weight. Then add edges into the graph until the start and end node are connected (Test this using DSU). Then to find the path you can just DFS, only using the added edges.

Edit: Another simple algorithm would be to binary search for the answer, and to check if it is possible simply DFS from start, only using edges with weight >= value.

→ Reply