I fully support the caching of paths between cities/towns/other important areas! I suggest updating when new intelligence is obtained instead of just when roads are built, though, so that the towns do not have perfect knowledge of the world. Sorta like a fog of war in RTS/TBS games from the human player view.
For each city that is usable as an origin point you could generate paths to anywhere that it knows about (nearby cities/towns, enemy civ frontline cities or more depending on intel reports, etc) and create semi-permanent paths that are altered depending on changes to terrain such as forests being cleared to make travel easier or new road systems being built which make the current path less desirable. Updating those semi-permanent paths could be done using a variant on Dijkstra's algorithm confined to work within known information instead of perfect world state information. The paths would be stored within the origin's knowledge container using the destination as the key to search.
Example time of a possible implementation using cached paths and a limited tactical AI:
Towns A, B, and C exist. A is friendly with B, but mutual distrust exists between A and C.
A decides it is time for war and so wants to send some troops over to C. Town A could just send their troops directly to C, but recently got intel saying that C has started to build up defensive structures along the route A<->C but not B<->C since C is perfectly happy with B at the moment.
A decides instead it will send the army on a roundabout journey to bring it to C from the side without defensive structures, using the route from B->C. A sends army to B via a static route that is already known, but the army doesn't have a map (semi-permanent route) to follow to get to C. Army has two choices, ask B for a route to C (may or may not succeed depending on how much B likes C) or make a new path from B to C using a best-guess about the terrain situation. Let's say that town B decides to give the Army the route, and so A's army now goes and rampages C from the side in a surprise attack, survives, and wants to return home. The Army would have been given a map for the original A<->C path since they may have needed to head back to A if their intel was wrong about the B<->C route being open and more heavily defended than A<->C. Army then heads along the A<->C route (backwards since their origin is C and destination A) and gets home safely.
A lot of ways to go about the tactical AI portion, the above being a poorly formatted and simplified version. Hope reading it doesn't make your head hurt (from parsing it, not understanding it)