[Routing] Routing algorithms

[Nic Roets]

Hello Stefan,

The requirements you've stated are quite "general", so I can't thing of any
other algorithm than brute force. Something like a depth first search that
takes exponential time.

In fact, I think it would be possible to rewrite the traveling salesman
problem (for which no efficient algorithm yet exist) to fit your
description.

But if you list indicated the total number of edges involved, the maximum
number of edges that c(E) depends on, the time and processing power
available etc, we may be able to help you.

On Sat, Sep 20, 2008 at 5:34 AM, Stefan Pflumm <stefan.pflumm at web.de> wrote:

> Hello,
>
> I'm searching for an routing algorithm who can handle this two properties:
>
> 1. the edge weight function c(E) of the edge E depends on the costs of
> the predecessor edges. A* for example, can't handle this, because it
> connects existings paths without updating the successors. If the path
> previous to an edge changes and the edge is already expanded the costs
> of the edge and all successors will also change.
>
> 2. the edge weight function c(E) of the node N depends on the successor
> edge. For example: E_1 and E_2 are neighbour edges of E. c(E) to E_1
> must be not equal to c(E) to E_2
>
> I hope somebody can give me an advice, thanks
>
> Stefan
>
>
>
>
>
> _______________________________________________
> Routing mailing list
> Routing at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/routing
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20080920/9845b7e4/attachment.html>