Sounds better the more I think about it, might be some problems with this, but I'll try this.
But "Immediate surroundings"? Like for every node in the path I shall increase the cost of all its neighbouring nodes also?
Yup, to spread the units naturally, but keep them kinda grouped at the same time.
If you've ever played Cossacks, you might have noticed the wonderful AI. They used cost-algorithms that did not only take terrain into account, but also their own and the enemies 'influence'. Just as much as they attract eachother, they will repell.
Just take the average walk on the street, you can pretty much visualize the influences and the 'logical' path you travel through people moving at different speeds and in different directions. You don't need interconnected nodes, just a couple of Vec2 and Vec1 for different kinds of influences, which will influence (yet again) the travel-cost through the nodes.
I've never implemented this myself, hardly any pathfinding, except quite fancy
gridbased floodfill. So if there are giant practical problems, don't blame me