You are not logged in. Please login at www.codechef.com to post your questions!

×

AMR14B - Editorial

PROBLEM LINK:

Practice
Contest

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Dijkstra's algorithm, Prim's algorithm

PROBLEM:

Given an undirected weighted graph, find whether there exist a shortest path tree(rooted at node 0) which is also the minimum spanning tree.

QUICK EXPLANATION:

If the weight of the Minimum Spanning Tree(MST) is equal to the weight of some Shortest Path Tree then the answer is YES else NO. Now among many shortest path trees, only the one whose weight is minimum can possibly also be the minimum spanning tree. So to find the shortest path tree with minimum weight we have to modify Dijkstra's algorithm such that if there exist more than one path to a vertex from root which yields the same distance from root then we give preference to that path whose last edge added is minimum.

EXPLANATION:

Weight of any tree is greater of equal to weight of MST,therefore weight of any SPT will also be greater or equal to weight of MST. So if any SPT has weight equal to weight of MST, then that SPT is also a MST since it connects all vertices. Now, the question basically boils down to finding the minimum weight shortest path tree(rooted at vertex 0). Once we find the weight of that tree and if it is equal to weight of the minimum spanning tree(MST) then answer is YES else NO. See the example below where there are 2 shortest path tree(SPT) and one of them is also the MST.

image

Now to find the minimum weight shortest path tree we will modify the standard Dijkstra. In Dijkstra, we initially assign distance equal to 0 to vertex 0 and insert pair < distance, vertex > = <0,0> into a heap. Then we repeatedly extract min and relax all the neighbours and insert the pairs whose distances are reduced. Now instead of that we will insert a triplet < distance, lastEdge, vertex >. So the heap structure will first follow the distance field and if distances are equal then it will follow lastEdge field. We can note this in the above graph, when vertex B is extracted, the algorithm will insert two triplets <22,2,C> and <30,10,D>. Then vertex C will be extracted and the triplet <30,8,D> will be inserted. Now notice that there are 2 shortest paths from A to D (A-B-D and A-B-C-D) but the path A-B-C-D should be preferred and this is exactly the case here as while inserting <30,8,D> we will update the lastEdge added. Below is pseudo code of the main loop of the modified Dijkstra.

priority_queue<triplet> Q;
Q.push(0,0,0);
while(Q is not empty) 
    u = Q.third;
    Q.pop();
    if(visited[u]) continue;
    for all neighbour (w, v) of u where w is the edge weight
        if( !visited[v] && (dist[u] + w < dist[v] || (dist[u] + w == dist[v] && w < lastAdded[v])) )
            dist[v] = dist[u] + w;
            lastAdded[v] = w;
            Q.push(dist[v], lastAdded[v], v);
    visited[u] = true;

Now we just have to add all the values in lastAdded array and that will be our answer which is compared with weight of the MST. Further we also have to take care of the case when graph is disconnected, which can be easily accomplished by initializing lastAdded to infinity. After running the modified Dijkstra, if any of the vertex has lastAdded[] set to infinity then the answer is NO.

The proof of correctness of this algorithm is same as that of proof of correctness of prim's algorithm which can be found in Introduction to Algorithms by CLRS.

EDITORIALIST'S SOLUTION:

Editorialist's solution can be found here.

This question is marked "community wiki".

asked 14 Jan '15, 23:17

saurabh060792's gravatar image

4★saurabh060792
1951916
accept rate: 0%

edited 16 Sep '15, 16:05

admin's gravatar image

0★admin ♦♦
17.4k347486515

excellent editorial! +1 for actually posting your solution instead of a dead link.

(15 Jan '15, 06:56) ironmandhruv4★

Would this algorithm work ? Gave WA's in contest.

We compute the shortest distance to each node using Dijkstra and also find the sum of edges of the minimum spanning tree.

Then we modify Prim's minimum spanning tree algorithm to include only those edges at each step which gives the node to be included in tree a distance equal to shortest distance computed by Dijkstra.

If we are able to build such a tree with cost equal to cost of minimum spanning tree then "YES" else "NO".

link

answered 07 Oct '15, 10:39

adityaakash's gravatar image

4★adityaakash
1
accept rate: 0%

Can any one please help me out here, why do i get run time error most of the time. And worst thing, i can't see any successful submission in java. Here is my code. http://hastebin.com/zidakuqufu.avrasm

link
This answer is marked "community wiki".

answered 07 Oct '15, 22:37

mukarram_ali's gravatar image

2★mukarram_ali
1
accept rate: 0%

Practice and Contest Link is swapped.

link

answered 08 Oct '15, 19:55

ninjascript's gravatar image

3★ninjascript
1
accept rate: 0%

GEtting WA ? inputs anyone ? java code https://www.codechef.com/viewsolution/8860386

link

answered 04 Dec '15, 12:55

sanket407's gravatar image

4★sanket407
4648
accept rate: 11%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×12,235
×1,081
×138
×37
×14

question asked: 14 Jan '15, 23:17

question was seen: 3,718 times

last updated: 04 Dec '15, 12:55