# Path search algorithms on graphs

Consider a directed graph and two vertices on it. I need to determine is there a path between them. There is a "breadth-first search" ("wave algorithm" in Russian) algorithm (see description below).

Question What are the alternatives and is it known what kind of algorithm has less complexity on some specific types of graphs, e.g. random graphs, "sokoban-graphs" (see below) ?

Roughly speaking breadth-first algorithm - look at ALL paths outgoing from "A" of length 1, next step of length 2, next step length 3, ...

It has clear intuitive disadvantage if graph is "very connected" - we are looking for too many "short paths" - it would be better to take one "long path" which goes from vertex "A" "somewhere near" to destination "B", and then find path from "somewhere nearby B" to "B" by "breadth-first" search. Of course, here we should somehow be able to explain what means "somewhere near" and propose a strategy to find a path from "A" to it. For some classes of graphs - "trellis graphs" this is clear what means, I do not know in general.

Motivation comes from the question

Algorithm to solve Sokoban-like game on graphs - move chips from one set of vertices to another

The problem about chip movement or sokaban like problem can be reduced to the question of existence of the path between the two vertexes. However the graph appearing here is quite specific - vertices of the "big-new-graph" are configurations of chips on the original graph and they are connected if there is a "MOVE" from one configuration to another.

So taking these specific properties of that graph what algorithm should one use to settle the path existence problem.

-