The shortest sequence of nodes, although an unweighted graph

Question

I would like to know if there is an algorithm for finding the shortest sequence of nodes, although the graph from its head is node to tail is node. The graph branches from the head of the node and is arbitrarily complex and converges at the tail of the node. All connections between nodes are weightless.

I consider the solution to this problem using the search steps from the head and tail nodes and until the nodes at either end of the graph touch, etc., but I would like to know if there is a “better wheel” before) come up .

Answer 1

Use the width of the first search , which works in O (E + V). This is the fastest thing you get on an unweighted chart.

Answer 2

This is one of the most beautiful "standard" problems of computer science. Given your description of the chart, you should first look at Dijkstra's algorithm

Answer 3

BFS is best suited for these types of problems, even if you want to find the shortest node path that you will go through the entire graph to find if there is another possible path other than the shortest path already obtained.

You can also draw a BFS tree that tells you exactly the shortest route between the source and any (also one) node.