How to quickly find a point on the right path through the maze?

Question

Algorithms

I welcome everyone.
There is a labyrinth

Answer

Arrows in hexagons - determine the possible directions of movement.
Number of arrows in one direction - determines the number of steps to stop when moving in the specified direction (for example, three arrows - only three cells).
The entrance is a gray hexagon with arrows, on the left.
The exit is a gray hexagon without arrows, on the right.
It is necessary to determine whether a randomly selected hexagon is on the correct path (moving from the entrance to the exit with the specified criteria must have a solution) from the entrance to the exit of the maze in the minimum number of checks when finding the path (i.e., only the yellow hexagons from the image - response).
What is the fastest algorithm to solve this problem? (and can lookup times be significantly reduced using async or waves?)
Thank you!

Answer 1

I will supplement the answer Sergey .
The Floyd-Warshall algorithm operates when calculating the distances between 3 points and the matrix will need to be calculated all. The Bellman-Ford algorithm is mainly used for graphs with negative edge weights - it looks for cycles, its application in this example is like this. Dijkstra's algorithm uses a breadth-first search (BFS), i.e. calculates the entire graph simply with positive weights, unlike Bellman-Ford.
Therefore, if you do not care about the optimal path (read the shortest), then use the graph bypass in depth (DFS) - it will tell you faster on average whether you will reach, i.e. for the minimum number of checks when searching.

Answer 2

I'll add to rPman 's answer - breadth-first search is the fastest in this case. I don't quite understand why

I thought it was long!

, because the complexity is O(V+E), where V is the number of vertices and E is the number of edges; for this case, V=70, E=138, generally a penny. Maybe you don't understand it correctly?
I'll show you how I did it - first I built an adjacency list for this graph, numbered it like this:
it turned out

adjacency list

1: 2 9
2: 6 14
3: 12 22
4: 9 20
5: 7 26
6: 11 13
7: 5 3
8: 4 16
9: 8 30
10: 5 20
11: 18 7
12: 11 26
13: 8 15
14: 22 18
15: 22 24
16: 22 45
17: 5 19
18: 12 40
19: 20 29
20: 21 10
21: 42 23
22: 23 3
23: 33 21
24: 32 35
25: 8 35
26: 12 39
27: 36 48
28: 47 7
29: 28 61
30: 20 14
31: 28 54
32: 55 53
33: 30 34
34: 46 16
35: 34 46
36: 38 26
37: 29 27
38: 48 49
39: 20 65
40: 30 66
41: 64 43
42: 54 39
43: 40 14
44: 43 46
45: 33 46
46: 34 44
47: 17 28
48: 40 37
49: 47 51
50: 37 52
51: 50 27
52: 60 19
53: 65 67
54: 53 42
55: 22 70
56: 48 57
57: 56 28
58: 57 39
59: 62 30
60: 59 65
61: 58 42
62: 41 69
63: 67 31
64: 68 60
65: 69 66
66: 67 54
67: 66 53
68: 
69: 65 66
70: 69 63

and a simple implementation of bfs in ruby

data = File.read('input.txt').split("\n").map { |line| line.split(":") }.map {|item| [item[0].to_i, item[1].split(' ').map(&:to_i)]}.to_h
puts data # {1=>[2, 9], 2=>[6, 14], 3=>[12, 22], ...

queue = [1]
visited = [1]
prev_vertex = {1 => -1}

while queue.any?
  vertex = queue.shift
  data[vertex].each do |neightbor_vertex|
    next if visited.include?(neightbor_vertex)
    queue << neightbor_vertex
    visited << neightbor_vertex
    prev_vertex[neightbor_vertex] = vertex
  end
end

vertex = 68
path = []
while vertex != -1
  path << vertex
  vertex = prev_vertex[vertex]
end

puts path.reverse

the code on this graph needs 68 steps to go forward, and 35 steps back (to build a list of vertices in the optimal path),

answer

1
2
6
13
15
24
32
55
70
63
31
28
47
17
19
29
61
58
57
56
48
37
27
36
38
49
51
50
52
60
59
62
41
64
68

same.
If I misunderstood the question or the linear complexity is still long, then it’s worth clarifying the dimension of the graph, and thinking in the direction of parallel bfs

Answer 3

A normal breadth-first search with traversal marks, since you don't have weights on the edges, will find the optimal 'fastest' path. You can't tell if a given cell is on the optimal path until you find it, so - during breadth-first search you have a list of current solutions, as soon as at least one solution is found, you stop searching and check if the specified vertex is located on one of the paths (there may be several at the same time).

Answer 4

I think you need to create a graph where each cell is connected to others that it points to and find the path with some algorithm.
These are the ones
, maybe there are better ones