Shortest path routing algorithm efficiency ideas

[aelalaily]

Hi,

I am designing a routing algorithm for a project I'm working on. I have a graph that has 100 nodes, and each node is connected, on average, to 4 nodes.
The nodes and connections are stored at two global arrays. I get as an input, the starting node and the ending node and try to compute the shortest path between those nodes.

The algorithm I designed, takes the starting node, and adds each of its connections to an array of possible paths. Then takes each of those nodes, checks their connections, and adds all the nodes they are connected to the array of possible paths. It does not add nodes previously on that possible path (no loops). Till either the end node is reached or the depth limit is reached (13 nodes). The problem with that, is it's extremely inefficient.

In the beginning I used to terminate the search after one million possible paths. But when it came to testing the algorithm, I found out that it gives poor results. I kept trying with a bigger number of paths. I have reached 15 million paths and it still does not give out optimal paths, while still taking a lot of running time.

I am trying to think of a way to increase the code complexity, that would decrease the running time. Any ideas? Or is that a wrong approach to take here?

Any help will be much appreciated!

[coder777]

Yes, that's the Travelling salesman proble. You might look here http://en.wikipedia.org/wiki/Travelling_salesman_problem

Out of fun I implemented the 'Ant colony optimization algorithm' look at http://en.wikipedia.org/wiki/Ant_colony_optimization_algorithms

[z05DSL3A]

The other day I read an MSDN magazine article, Use Bee Colony Algorithms to Solve Impossible Problems, I now I'm going to have to compare Ants and Bees to see how similar they are...
http://msdn.microsoft.com/en-us/magazine/gg983491.aspx

[aelalaily]

Oh.. I did not consider search optimizations before.

Thank you both very much!

[ne555]

I get as an input, the starting node and the ending node and try to compute the shortest path between those nodes.

The algorithm that you describe is Breadth first search. O( |V| + |E| ) ~ O(n²)
So, with your constraints it should work.

Maybe your loop check is failing.

edit:

It does not add nodes previously on that possible path (no loops)

It should not add any node that was already added.
You should not change your branch, because the other is shorter

[webJose]

Grey Wolf, that article sure was very interesting. The actual sample, though is far from usable, I would say. I ran multiple tests (after making the random seed the tick count of today's date (truncated to int), and it is quite inconsistent. But of course, there is one major flaw in the implementation (IMHO): The code allows the bees to repeat visited food sources by other bees. I am guessing the implementation will be (far?) more efficient if it kept track of visited sources.

Maybe a hash table, or simply a sorted array of 64-bit numbers that represent the permutation number (if elements were ordered by name and changed orderly, like from left to right or right to left).

In any case, it is a very interesting approach.

[bartoli]

If you are using STL containers, be sure to measure time on the release version of the program, not on the debug version. For an algorithm in a program i work on, in debug mode, by just iterating over a vector instead of using[] in a loop, iterators were 20 times slower!