[boost] How to speed up the djikstra graph

Subject: [boost] How to speed up the djikstra graph
From: Lennart Berg (LB_at_[hidden])
Date: 2009-05-21 19:12:09

Hi Everybody

I have had the pleasure of using the boost graph library for my project now,
but I have ran into some problems, that I hope you can guide me on.

First of all, let me tell a little about the project.
I am a third party developer for paradox interactive, making an expansion
for one of their games.

Now i have implemented the djikstra alghorithm to simulate the transport
capacity of countries, and it works pretty well.
However I still think that the speeds to be improved somewhat (takes about
1-2 secs to compute), to make it more playable.

First of all the map consists of ~2500 provinces / vertexes each with 4-8
edges / neighbours.
I Find all the provinces I can access and then add all neighbours from it as
edges.
Each edge is allocated a cost according to infrastructure, terrain and
distance from orgin to destination.

Each "round" of the game is an hour, so a day is effectively 24 rounds.
Right now I make a new graph once every day, one separate graph for each
country, and compute it for every country once a day.
However as the game has up to 300+ countries that becomes a pretty harsh
computational burden.

Now pretty much every variable in this setup can change hourly. ( location
of units, conquest / loss of provinces, destruction of infrastructure,
expansion / repair of infrastructure)
So the question is how I can improve this approach.

Optimally the graph should be persistant and allow me to dynamically add /
remove provinces and change the cost of the edges every hour (as I
understand it the boost library allows that right now with vertex_clear /
add etc.), and giving new values without recomputing every single edge in
the graph 300 times every hour.
Is that possible? And if how would that be done?

Thanks in advance
Lennart Berg