Maintaining Roads

Computer Science Level 1

The diagram below shows the time it would take to travel on each of the roads connecting these 8 towns. People always travel on the shortest path. Which of the roads should be shut down due to lack of use?

The answer $A\leftrightarrow B$ represents the road connecting town A and B.

1\leftrightarrow 3

2\leftrightarrow 5

4\leftrightarrow 5

7\leftrightarrow 8

1 solution

展豪張
Aug 29, 2016

Look at the triangle with vertex number 3, 4, 5.
We can see that the path 4-3-5 has length 2 but path 4-5 has length 3.
The road 4-5 should be shut down.

That is an excellent observation. How would you solve this problem for a more general graph?

Agnishom Chattopadhyay - 4 years, 9 months ago

Thank you! I have some thought but I think it is not efficient. First, the edge to be removed must be in a loop, otherwise some vertices will be isolated after the removal. Then apply shortest path algorithm to every pair of vertices and see which edges are not used at all (this is the inefficient part). Those edges are to be removed.

I think that there are better algorithms but I haven't learn that. I would be grateful if you could give me some keywords on this topic so that I can google it :)

展豪張 - 4 years, 9 months ago

I think a simpler way is to apply Floyd-Warshall's Algorithm. It's basically what you described : apply shortest path algorithm to every pair of vertices. Then, if the shortest path from A to B is shorter than the length of its directed edge, that edge can be removed. Overall this takes $O(V^3)$ where $V$ is the number of vertices. I think this can still be optimized although I don't have the idea now.

Christopher Boo - 4 years, 9 months ago

@Christopher Boo – Yeah, sorry, that does work. I was just confusing myself.

Agnishom Chattopadhyay - 4 years, 9 months ago

Have you heard of Minimal Spanning Tree algorithms?

Agnishom Chattopadhyay - 4 years, 9 months ago

@Agnishom Chattopadhyay – Wait! Minimal Spanning Tree cannot solve this problem. MST is to construct the subtree such that all towns are connected and the total road lengths is minimized. If town A, B and C forms a triangle with side length 1, MST will remove one of the side but none of them should be shut down.

Christopher Boo - 4 years, 9 months ago

why not 2->5 ?

A Former Brilliant Member - 4 years, 9 months ago

because 2 -> 5 offers a shorter alternative than the 2135. the 25 path is 7 while the 2135 path is 8. So the 25 path is a useful shortcut

Roshni Merugu - 4 years, 9 months ago

thank you, the picture was not clearly visible back then

A Former Brilliant Member - 4 years, 9 months ago

Maintaining Roads

1 solution

0 pending reports