Hello to all!
We have been studied graphs in school but it was not in depth. Now I'm
given a graph (network) under the following rules:
*) There are about 20-30k nodes
*) Every node connects to 1-4 other nodes
*) Size of every connection is a '1' in both ways - it doesn't matter
if you travel from vertex A to vertex B if there is an edge A-B. In
that way we can say the graph is unweighted and undirected, right?
Almost every algorithm I've found on the net is for directed, weighted
graphs (Dijkstra,Bellman-Ford), so I've come with another algorithm of
my own. I think it is a bit too complicated and it would run slow. I
haven't had the chance to test it yet. I don't know if I reinvent the
wheel? :)
Let's call it the algorithm of two circles.
Its base lies in the geometry where the shortest path between two dots
passes through the contact point of the two circles with equal radius
drawn around the two dots.
In that algorithm we have circles, which are build by nodes.
*) A circle with radius 1 features all the nodes which are connected
to node A. We say node A is the center of that circle.
*) A circle with radius N features all the nodes which are N-edges
away from the center.
It is essential for the algorithm to do not use previously used nodes.
We build two circles around the two points, from which we want the
shortest path. If they don't have contact points we expand each circle
with radius '1' and check again for contact points. When we have a
contact point then we have the shortest path.
Lets keep that more organized. Lets build trees from nodes - each
level of the tree is a circle with radius which is '1' bigger than the
previous. When we have a contact point (one of the first tree node is
found in the second tree) we can easily track down the path up to the
trees' roots.
Example:
We have the following graph:
Node: | connections to:
1| 2,3,5
2| 1,5
3| 1
4| 10
5| 1,2,7
6| 1,7,8,9,10
7| 5,6
8| 6
9| 6,11
10|6,4
We need the shortest path between 2 and 11.
We come to the following trees:
2 11
/ \ |
1 5 9
/ \ \ |
3 6 7 6
Here is the way: 2-1-6-9-11
Please post any comments on that algorithm, especially comments on the
speed and memory requirements.
If you know faster|simplier algorithm I'd like to know.
Best regards, Ivan.
|
