Boost logo

Boost :

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


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk