Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer 1

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.

share|improve this answer
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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