Task

For a maze generated by this task, write a function
that finds (and displays) the shortest path between two cells.



Note that because these mazes are generated by the Depth-first search algorithm, they contain no circular paths,
and a simple depth-first tree search can be used.




F dijkstra(graph, source)
   V n = graph.len
   V dist = [Float.infinity] * n
   V previous = [-1] * n
   dist[source] = 0
   V Q = Array(0 .< n)
   L !Q.empty
      V u = min(Q, key' n -> @dist[n])
      Q.remove(u)
      I dist[u] == Float.infinity
         L.break
      L(v) 0 .< n
         I graph[u][v] & (v C Q)
            V alt = dist[u] + graph[u][v]
            I alt < dist[v]
               dist[v] = alt
               previous[v] = u
   R previous
 
F display_solution(predecessor)
   V cell = predecessor.len - 1
   L cell != 0
      print(cell, end' ‘<’)
      cell = predecessor[cell]
   print(0)
 
V graph = [
    [0,1,0,0,0,0],
    [1,0,1,0,1,0],
    [0,1,0,0,0,1],
    [0,0,0,0,1,0],
    [0,1,0,1,0,0],
    [0,0,1,0,0,0]
]
 
display_solution(dijkstra(graph, 0))