Interesting, I assumed the roads were not going to change frequently (but rather, in bursts). So I used that premises to develop my algo. To enforce this behavior (on a code level), I will be adding a "planning" mode, where roads can be placed freely/frequently. Once the user sends the plan off to be constructed, then the graph will update. I may go one step further and have construction (i.e. graph updating) only happen at night, and give the user something else to do while its updating.

That being said, if they have a modern machine, then there will be no need for this at all (just need to figure out the avg user CPU GHz & core count). It takes 10 seconds for my algo to find the all pairs/all possible shortest paths between two nodes on my machine for 10,000 nodes, which by that point is a HUGE city.

The reason I did not go with A* is because it doesn't scale to 100K+ units and it always chooses the same path.