There are 100 towns labelled with 1, 2, ..., 100. We want to connect them all and it costs max{|i − j|, 4} to build a bridge between town “i” and “j”. However, when it comes to a bridge between town i and 2i, we can build bridges at a cost of 2 only. What is the minimum cost to create this connected graph?
So it would cost 30 to build between town 31 and 61, 4 to build between town 31 and 32, and only 2 to build between town 30 and 60. I know the minimum spanning tree algorithm that is used to find the cheapest path, but with the extra given condition of towns that are multiples of 2 of each other, how would i make change to the minimum spanning tree algo to find a connect graph?
The minimum spanning tree algorithms work with any (non-negative) weigths, so you don't need to modify them, you can apply them and they will give you one minimal solution.
Of course the special weigths given here make it possible to do that by yourself on a piece of paper, without an actual computer to run a program.
One MST algorithm starts with all vertices and no edges, and in each step just adds the cheapest edge that doesn't produce a circle, until you have a spanning tree.
The cheapest edges in this problem are the ones costing $2$ between $i$ and $2i$ ($i=1,2,\ldots,50$).
The algorithm will add all of them to its graph, because they don't form circles, instead they form distinct chains:
$$1-2-4-8-16-32-64,$$ $$3-6-12-24-48-96,$$
a.s.o., starting with each odd number below $50$ until $49-98$.
Then all the $2$-cost edges are already in the graph, the next cheapest edges are the ones costing $4$ between $i$ and $j$ where $|i-j| \le 4$ (and they aren't in the $2$-cost set, like $1-2$). That is especially true for $j=i+2$, so you can just connect the
$$1-2-4-8-16-32-64$$ and the $$3-6-12-24-48-96$$ chain with an edge between $1$ and $3$, the $$3-6-12-24-48-96$$ chain and the $$5-10-\ldots$$ chain with an edge between $3$ and $5$, a.s.o.
This creates an MST, the cost of which you can now calculate yourself!