Re: [boost] How to speed up the djikstra graph

Subject: Re: [boost] How to speed up the djikstra graph
From: Topher Cooper (topher_at_[hidden])
Date: 2009-05-22 10:09:04

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.
>