There is some pseudocode on the Wiki:

BFS(start_node, goal_node) { return BFS'({start_node}, ∅, goal_node); } BFS'(fringe, visited, goal_node) { if(fringe == ∅) { // Целевой узел не найден return false; } if (goal_node ∈ fringe) { return true; } return BFS'({child | x ∈ fringe, child ∈ expand(x)} \ visited, visited ∪ fringe, goal_node); }

But it has a lot of incomprehensible, namely the last line of the return function.

The essence of the job is to write a program to bypass the graph in width to find all the shortest paths. The essence of the question is to write pseudocode, which can pass the graph with the criteria above.

Now I have a working code that returns one shortest answer and that is to say the least very badly.

How it works?

  • We get a new vertex .;
  • We drive it into a function, mark it with black;
  • Check adjacent vertices and if they are white, we throw into the queue;
  • For each element, we remember its parents in a separate array of parents;
  • Next, spin in a circle until the queue is empty;
  • After the function is completed, we start the path recovery function, which restores the path reversely, starting from the final vertex and ending at the initial one, using the array with the parents.

It remains only to figure out how to make the program find all the shortest paths and do a normal search for an answer to the points passed, if this is really done (for the reverse search code looks disgusting).

  • Are you sure that you need all the shortest paths? There may be a lot of them. - pavel
  • The @pavel point is that the graph is provided for the problem and there are only 2 shortest paths in it, each 3 peaks in length. In general, these tasks are purely for learning, but I don’t understand something about how to do it with "straight arms", and not like mine. - Telion
  • the dynamics is the simplest then ... But the ways to restore later - pavel
  • @pavel could you set an example in any C-like language or write some sketches of code / pseudocode? To go through all the vertices and mark them in a black matter for 5 minutes, but somehow I could not record the check and the answer to the answer in a recursive version of the solution. - Telion

1 answer 1

I write an algorithm more simple to understand.

Start the queue from the starting point. Val is an array of distances from 1 point to all others. After that you have to start the queue from the finish cell and go only if Val[cur] == Val[new] + 1 . The value in those cells that we have not visited, you need to set to infinity.

Now we have cells that exactly enter at least 1 optimal path. You need the paths themselves, you want recursion, and you can.

 функция (параметр текущая клетка) --> набор путей для каждой соседней по стороне клетке если Val[cur] == Val[new] + 1 то вызовём функцию с новой клеткой добавим в список путей всё что нам вернули, приписав нашу клетку в каждый

Run from the starting point.

Importantly, the number of paths can grow exponentially (or close to it). If you need only the number of such paths then use memoization.

  • The queue at the end of the function should be empty otherwise the output will not occur, do you propose to save it for the passage in the opposite direction? And what do you mean by Val[cur] == Val[new] + 1 , is this a search for adjacent vertices? - Telion
  • not. You somewhere store the array is not the queue itself, and the distance from 1 point to those that have reached. By the way, do not interrupt the queue as soon as you reach the desired peak. - pavel
  • The distance in the plan between the points? They are all equal. There is no distance from the initial to the final. For now. This is if you know it, you can run the same pass only with a departure above this value. I understood correctly? - Telion
  • Okay, read the updated answer. You are proposing to make an array with distances from the starting point to the rest, right? Hmm .. That still needs to be figured out how to make it. - Telion