HISPDNET algorithm

general
1

Problem statement: http://opc.iarcs.org.in/index.php/problems/HISPDNET

I can only think of the following:

  1. Brute force: Consider all permutations of 2,3,4,…,N and find which among these gives the minimum cost (where the 1st city of the permutation is connected only to 2nd element, 2nd element to 3rd element and so on). But it is too time consuming and wouldn’t give the answer even in a billion years.

  2. Use some shortest path algorithm. (As of now, I am only familiar with Dijkstra’s and Floyd Warshall). But there is a big restriction, I need to find shortest paths between all pairs of sources and destinations and where the number of intermediate edges is strictly N-2 (excluding source and destination), nothing more or nothing less.

I am really confused as to how to approach the problem with an elegant time efficient algorithm. It would be great if someone could give me a hint.

2

I’ll give you a hint. Do you know how to efficiently find the articulation points in a tree? What’s the articulation point in the Government’s tree? How do you fix that with the lowest cost?

3

Oh no! I have no idea about articulation points! I guess I should get familiar with that first before proceeding further. Thanks a lot! :slight_smile:

4

The actual solution doesn’t depend on the algorithm to find articulation points, but you (at least I did) seriously get a lot of intuition to solve this problem efficiently.

5

It’s a direct application of a certain graph algorithm. I don’t think you can do spoiler text here so click here for solution: http://paste.ubuntu.com/9729050/

1 Like
6

@idraumr @superty Thanks again! I clicked on your solution link, but ended up blinking at the sight of ‘minimum spanning tree.’ That’s something new. I’ll understand how it works and then solve this problem :slight_smile:

1 Like
7

Please find the Errors in my code to Compute all the ARTICULATION POINTS in an undirected graph…http://cpp.sh/5qus