The Gateway to Computer Science Excellence
+29 votes

Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum  weight amongst all those edges that have one vertex in $X$ and one vertex in $Y$.

Let the weight of an edge $e$ denote the congestion on that edge. The congestion on a path is defined to be the maximum of the congestions on the edges of the path. We wish to find the path from $s$ to $t$ having minimum congestion. Which of the following paths is always such a path of minimum congestion?

  1. a path from $s$ to $t$ in the minimum weighted spanning tree

  2. a weighted shortest path from $s$ to $t$

  3. an Euler walk from $s$ to $t$

  4. a Hamiltonian path from $s$ to $t$

in Algorithms by Veteran (105k points) | 1.9k views

Yes, (A) is the correct answer.
To make this question understand in layman language, there are many toll gates from electronic city to Bangalore airport.
The condition to pay the toll is, that I have to pay the amount equal to the maximum of all the amounts charged by any of the toll gates

Path 1 - There is only one toll gate from electronic city to Airport, and that toll gate charges 60 rs.
Path 2 -  There are 10 toll gates on the another way from electronic city to airport, and all of the toll gates charge 8-8 rupees only or may be not more than 10 rs by any toll gate.

My aim is to the save the money then i will take path 2, as i have to pay maximum 10 rs only.

can somebody tell me what does congestion mean in this question

say s=A and t=C,

Path with minimum congestion is the directly given edge. 

If in minimum spanning tree if AC edge is not included then the path with minimum congestion will be A-D-F-C which is not minimum. So option a is wrong and option b is correct.


@sunil,in question it is mentioned that "Let s and t be two vertices in a undirected graph G=(V,E) having distinct positive edge weights".

When we apply Prim's algorithm, we are basically finding the path of least congestion. That's because we are always choosing the lightest (least congested) edge and so we are guaranteed to find the least congested path from the starting vertex to every other vertex.
Can someone please explain what a congestion is?

3 Answers

+24 votes
Best answer

Here answer should be A.

Here, shortest path will give $6$.
Spanning tree contains edges of weights $2$,$3$,$4$ so congestion in this case is $ \max (2,3,4)$, that is, $4$. For path $s$ to $t$, overall congestion is $\max(3,4) =4$ but total weight is $7$.

Option $C$ and $D$ are I think not related to this question.

by Boss (25.6k points)
edited by

Consider the following graph

In this case minimum weight spanning tree is  s - a - b - t and s -a is the minimum weighted edge but the minimum congestion path from s to t is s - t having congestion 11. Shouldn't the answer be option B?

In mst a to b should not included ...

Mst for Ur graph will be...

s-a  , s-t and t-b  

Use kruskal for clear picture !
You are right, i was finding the mst incorrectly, thanks.
edge congestion means interconnected network so here the s and t is a vertex which is connect with every vertex???????????????

they are jus telling us to assume the weights as congestion thats ol

nothing else to be infered from that
This is a beautiful question where you can witness the fact that in case of applying single src shortest path between two nodes, we are looking at the sum of edge weights along the path between the nodes as the deciding factor, whereas in the question above at any particular instant we look at the crossing edges and decide which one is the minimum so that every edge weight along the path is trying not to raise the upper bound (which increases congestion) even though reaching the destination may require a large number of edges.
+5 votes

Option A is Correct Only.

by Active (4.3k points)
+4 votes

This is also based upon the cut property of the spanning trees.

For the property, I refer you to theorem 23.1 of Cormen 3rd edition.

Consider I have below scenario where I have two components, X and Y and vertex s lies in X and vertex t lies in Y.

I have recursively further divided the component of X into two more components X1 and X2 having vertex A and B respectively.

Consider congestion of edge S-A=3,S-B=2, A-T=5 and B-T=2.

At every step, I choose light edge (minimum weight edge which joins two distinct components of the graph)

So, first I select edge S-B. Then I select edge B-T and this path to T from S via B is of minimum congestion. And this is nothing but how your spanning tree algorithm works. 


by Boss (29.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
104,917 users