This is a homework and I'd like your feedback on whether I'm on the right track. Thank you.

There's a project to build a railroad to connect $n$ cities. The railroad that connects any two cities can be done concurrently (so each track $i$ will complete in $t_i$ time from now). The cities and the roads that connect them are given as a weighted, undirected and connected graph with weights being the distances between the cities. Find the fastest schedule to build the railroad that connect all cities and indicate the earliest time when this railroad can be completed

I use a slightly modified version of Kruskal's MST algorithm. In particular, starting with a graph with all nodes and no edges, I add the edges one by one in order of increasing weights. The last edge that make all nodes connected is the earliest time of completion; and the resulted tree is the desired schedule.


Was "I'd like your feedback on whether I'm on the right track" intentional? At any rate, your solution looks fine. Depending on what's expected of your homework, you may have to prove that the last edge to be added did indeed determine the minimal completion time. By the way, welcome to math.SE.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.