Finding shortest path into unweighted undirected graph

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

.

Relevant Pages

  • Finding shortest path into unweighted undirected graph
    ... that way we can say the graph is unweighted and undirected, ... Almost every algorithm I've found on the net is for directed, ... to node A. We say node A is the center of that circle. ... Lets build trees from nodes - each ...
    (comp.games.development.programming.algorithms)
  • Re: Shortish paths
    ... For how many nodes and how many edges will the actual algorithm run ... original graph. ... optimal solution is removed from the graph, ... I intend to begin by rereading the shortest path sections of Cormen ...
    (comp.theory)
  • Re: Standard graph API?
    ... isomorphism graph library. ... It's pretty uniformly agreed that there is no standard graph ... the algorithm can't be specialized for the graph at ... My thought is to use some sort of templating system. ...
    (comp.lang.python)
  • Difference between two systems of DAGs
    ... I am looking for a graph algorithm, ... carry no label or other information except direction. ... edit operations are to change the label of a vertex or the ...
    (comp.theory)
  • Re: Vertex Cover implementation
    ... i code this simple greedy algorithm for the vertex cover: ... As you are constructing your graph you can update the vertex ... each edge appears on two adjacency lists. ... reason to use a priority queue for your algorithm. ...
    (comp.theory)