What is the most efficient way of finding a path through a small world graph?

I have a sea of weighted nodes with edges linking clusters of nodes together. This graph follows the typical small world layout.

I wish to find a path finding algorithm, which isn't costly on processor power, to find a path along the best possible path where the nodes are the most favorably weighted, the fastest route is not the most important factor. This algorithm, also takes into consideration load bearing, and traffic rerouting.

(sidenote: could neural networks be used here?)

Thanks

I'm looking at ACO. Is there anything better than ACO for this kind of problem?

Right the A* algorithm finds the least cost or fastest route, without load balancing.

Lets say that the fastest or shortest route is not the most important route, what is more important is following a path where the weighted nodes have a certain value. no1.

no2. If using A* the traffic on that route gets overloaded then suddenly that path is redundant. So as cool as A* is, it doesnt have certain features that ACO ie inherent load balancing.

-- unless im mistaken and misunderstood A*

Then what beats ACO?

It really looks like a show down between ACO and A* , there has been so much positive talk about A* , I will certainly look deeper into it.

Firstly in response to David; I can run ACO simulation in the back ground and come up with the best path, so yes there is an initial startup cost but the startup luckily isnt essential. So i can afford to run a simulation multiple times. The one real trouble is finding connected source and destination nodes. Whereas it seems A* will be able to do this quite easily. Now what happens when this network get dreadfully large like in millions of nodes. Will A* be able to scale easi

algorithm graph-theory path-finding

Edit Report

With A*, the path cost does not need to be constant, so you could start with the following graph:

A---1---B---1---C
|               |
\-------1-------/

where we want to go from A to C. Initially, the path finding algorithm will choose the A-C path since A-B-C is 2 whereas A-C is 1. We can add an extra term to the paths:

A---r---B---r---C
|               |
\-------r-------/

with

r(NM) = k(NM) + users(NM) / 10

where

r(NM) is the cost for a connection between N and M,
k(NM) is the constant cost for a connection between N and M,
users(NM) is the number of objects using the connection

As users are added to the system, the route A-C will become more expensive than A-B-C at twenty users (1 + 20/10) = 3, A-B-C is 2. As users are removed from the system, the A-C route will become the best option again.

The real power of the A* is the heuristic you use to calculate the cost of each connection.

answered 2008-10-21T10:55:58.730

What is the most efficient way of finding a path through a small world graph?

1 Answer

Your Answer