On a general point, I don't find upgrading roads terribly exciting, especially as http://en.wikipedia.org/wiki/Metcalfe's_law means that lots of cities means a huge amount of roads to look after. I would rather have a budget slider for road maintenance and then have the computer figure out where to spend the money. Roads organically growing in response to how much they're used appeals to me though.
I do think there's a specific difficulty with automatically building roads in that some towns will be completely inappropriate to connect because it is not really any faster than going via another city, and you would just end up with a tangled mess.
If CPU time is cheap enough for it, I would suggest you could get past this by:
#1 calculate the quickest route between the cities
#2 pretend the road has been built and recalculate the new quickest route between the cities
#3 If #1/#2 > some constant (say 1.1), then build the road, otherwise it's a pointless road and will probably look stupid so don't build it
Could probably also cache roads between cities as a network graph if the calculation is too slow, although obviously the game has a general solution for calculating optimal routes already which it uses with every automove, so this is probably not necessary.
There is a problem here though: sometimes rather than going between cities it will be most efficient for roads to connect to each-other. A solution for that is probably harder .