Just to be clear, are you computing the minimum total cost from a single initial point to all other accessible points within the country (single source shortest path problem) or are you computing minimum cost between all pairs of provinces within the country (all sources shortest path problem)? In the latter case, you should get a huge speed-up by using the Floyd–Warshall algorithm instead of repeated use of the Dijkstra algorithm. For the single source problem it's hard to see how you could improve on just repeating the Dijkstra algorithm for a dynamic graph -- even keeping around some form of traces of the original run -- since modifying the weight of any edge might switch the course of the algorithm to considering a path completely ignored originally. Without having thought it through too thoroughly, the information from a distance between all pairs of vertexes matrix (maybe with some trace info) might allow updating to be kept more localized. This might come out quite naturally from a slightly tweaked F-W algorithm, or perhaps from Johnson's algorithm (which is usually reserved for use in solving this problem for sparse graphs). In fact, it might be that you could get an overall lower cost by using F-W at the outset and then revising it, even if you really want the single-source shortest path problem (i.e., what Dijkstra's algorithm would normally be used for). I'm going to be traveling this weekend. Maybe I'll work on it, on the road. Topher Lennart Berg wrote:
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.