I didn't put it in the title, but of course this is a post about Advent of Code, in particular Days 16 and 18 which feature a perenial favorite type of problem: finding shortest paths in mazes.

Your input for these is always a maze given as an ascii map.  Like so:

###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#....#....#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S......#.#...#
###############

There's lots of ways to import one of these into Maple and then solve the maze, but I am to highlight how to do it with GraphTheory.  I am going to start with a GridGraph and then remove the walls in order to leave a just the vertices that represent the paths:

with(StringTools): with(GraphTheory):
maze:=
"###############
#.......#....E#
#.#.###.#.###.#
#.....#.#...#.#
#.###.#####.#.#
#.#....#....#.#
#.#.#####.###.#
#...........#.#
###.#.#####.#.#
#...#.....#.#.#
#.#.#.###.#.#.#
#.....#...#.#.#
#.###.#.#.#.#.#
#S......#.#...#
###############
":
mazelines := (Split(Trim(maze), "\n")):
sgrid := ListTools:-Reverse((map(Explode, mazelines)) ):
m,n := nops(sgrid), nops(sgrid[1]);
tgrid := table([seq(seq([i,j]=sgrid[i,j],i=1..m),j=1..n)]):
start := lhs(select(e->rhs(e)="S", [entries(tgrid,'pairs')])[]);
finish := lhs(select(e->rhs(e)="E", [entries(tgrid,'pairs')])[]);

Now the maze is stored in the table tgrid, and it is easy to find the walls and paths.  In a GridGraph the vertices are labeled with their coordinates as "x,y" and so we rewrite our list of paths in that form, so we can create the induced subgraph of the Grid that includes only those vertices.

(walls,paths) := selectremove(e->rhs(e)="#", [entries(tgrid, 'pairs')]):
paths := map(s->sprintf("%d,%d",lhs(s)[]), paths):
H := SpecialGraphs:-GridGraph(m,n);
G := InducedSubgraph(H, paths);

We can use StyleVertex to highlight the start and finish.

StyleVertex(G, sprintf("%d,%d",start[]), color="LimeGreen");
StyleVertex(G, sprintf("%d,%d",finish[]), color="Red");

plots:-display(<
DrawGraph(H, stylesheet=[vertexshape="square", vertexborder=false, vertexcolor="Black"], showlabels=false) | 
DrawGraph(G, stylesheet=[vertexshape="square", vertexborder=false, vertexcolor="Black"], showlabels=false)>);

(I omitted a step where I set the vertex locations of the maze grid, you can see that in the attached worksheet)

Now finding a path through the maze is as easy as calling GraphTheory:-ShortestPath

sp := ShortestPath(G, sprintf("%d,%d",start[]), sprintf("%d,%d",finish[]) ):

StyleVertex(G, sp[2..-2], color="Orange");
StyleEdge(G, [seq({sp[i],sp[i+1]}, i=1..nops(sp)-1)], color="Orange");
DrawGraph(G, stylesheet=[vertexshape="square", vertexpadding=10, vertexborder=false,
             vertexcolor="Black"],  showlabels=false, size=[800,800]);

Now, Advent of Code seldom gives you a completely simple maze like this, often these is a twist like having to calculate the costs of turns seperately from the cost of steps, or each direction or position has a seperate cost associated with it.

For example, Day 16 has us starting facing east, and then turns cost 1000, while moving forward costs 1. That sort of problem is no longer exactly a maze, instead of the vertices being representing an "x,y" position, instead you increase the number of vertices by a factor of 4, so that you have a vertex for every position and orientation "x,y,o" with edges of weight 1 between adjacent vertices with the same orientation and edges of wieght 1000 to connect "x,y,N" to "x,y,E" and "x,y,W" e.g.  In that sort of weighted graph, we can use GraphTheory:-DijkstrasAlgorithm to find the shortest path and it's weighted cost.

In this code, we expand our list of maze locations with directions, and the use the grid table to generate a list of weighted edges:

dtable := table([0=[0,1], 1=[1,0], 2=[0,-1], 3=[-1,0]]):
dname := table([0="N",1="E",2="S",3="W"]):
dpaths := map(s->local d;seq(cat(s,",",d), d in ["N","E","S","W"]), paths):

edges := NULL:
for i from 1 to m do for j from 1 to n do
    if tgrid[[i,j]] = "#" then next; end if;
    for d from 0 to 3 do
        dir := dtable[d];
        if tgrid[[i,j]+dir] <> "#" then
            edges := edges, [{cat("",i,",",j,",",dname[d]), cat("",i+dir[1],",",j+dir[2],",",dname[d])},1];
        end if;
        edges := edges, [{cat("",i,",",j,",",dname[d]), cat("",i,",",j,",",dname[d+1 mod 4])}, 1000],
                 [{cat("",i,",",j,",",dname[d]), cat("",i,",",j,",",dname[d-1 mod 4])}, 1000];
    end do;
end do; end do:

Gd := Graph(dpaths,weighted,{edges});

Once that is done, it's a simple matter of calling Dijkstra's Algorithm on the graph, but notice that we can reach the finsh while traveling north or east, so we need to find the sortest path to both (you can pass a list of vertices to Dijkstra, and it will efficiently calculate paths to all of them), and select the smaller of the two:

spds := DijkstrasAlgorithm(Gd, cat("",start[1],",",start[2],",E"), 
    [cat("",finish[1],",",finish[2],",N"), cat("",finish[1],",",finish[2],",E")] , 
    distance):
i := min[index](map2(op,2,spds)):
spd := spds[i];

spd := [["2,2,E", "3,2,E", "4,2,E", "4,2,N", "4,3,N", "4,4,N", "4,5,N", "4,6,N", "4,6,E", "5,6,E",
 "6,6,E", "7,6,E", "8,6,E", "8,6,N", "8,7,N", "8,8,N", "8,9,N", "8,10,N", "8,11,N", "8,12,N", 
"8,12,W", "7,12,W", "6,12,W", "5,12,W", "4,12,W", "3,12,W", "2,12,W", "2,12,N", "2,13,N", 
"2,14,N", "2,14,E", "3,14,E", "4,14,E", "5,14,E", "6,14,E", "7,14,E", "8,14,E", "9,14,E", 
"10,14,E", "11,14,E", "12,14,E", "13,14,E", "14,14,E"], 6036]

We can then plot to compare this to the unweighted shortest path:

dsp := ListTools:-MakeUnique( map(s->s[1..-3], spd[1]) );
StyleVertex(G, dsp[2..-2], color="DarkBlue");
StyleEdge(G, [seq({dsp[i],dsp[i+1]}, i=1..nops(dsp)-1)], color="DarkBlue");

DrawGraph(G, stylesheet=[vertexshape="square", vertexpadding=10,
             vertexborder=false, vertexcolor="Black"],  showlabels=false,
          size=[800,800]);

And you can see it's a path that requires more steps, but definitely uses fewer turns if we start facing east/right (6 vs. 9):

I hope this has given you a little bit of a flavor of how to use GraphTheory commands to solve path finding problems.  Like with the second part here, usually the biggest challenge is figuring out how to encode and construct a graph that represents your problem.  Then the actual commands to solve it, are easy. You can see all the code, and a couple steps I left out from above in this worksheet: Mazeblog.mw

And just for fun, here's a Maple workbook that imports a maze from an image and solves it: MazeFromImage.maple