# Thread: Shortest path between two points

1. ## Shortest path between two points

Hi all~

I am currently working on a maze solver and has tried the left-hand-rule method.
Now however, I am hoping to achieve the same by via the shortest route.

From the image above, with the leftmost red coloured 1 being the entrance and the rightmost red coloured 1 being the exit, and the @ being walls and . being open paths, I have walked through the maze via the path noted by 1s. It takes my method 8 steps (exclusive of start and end) but if you note the shortest path in yellow, it's only 6).

As I am only able to move horizontally and vertically (no diagonals), how can I go about devising a function with basic programming construct (recursive calls, loops, arrays) to get the shortest path?

I have looked online but have trouble understanding how the BFS and A* works, especially with conditions excluding diagonals...

Any help would be appreciated...!

2. BFS is actually not that hard. The basic idea is to use a queue to hold the adjacent positions that you haven't visited yet. (Do you know how to make a queue?)

Initialize the queue with the start position and then enter a loop. If the queue becomes empty, no path was found. Otherwise, pop the front of the queue (initially the start position) and mark that position as visited. If that position is the goal position, success! Otherwise, push all that position's neighbors that haven't been visited yet onto the queue. Repeat the loop.

In order to find the shortest path once the goal position has been reached by the BFS, you need to save which position added each new position to the queue. One way to do that is to store symbols into the character array itself, which might end up looking something like this:
Code:
```` 0 1 2 3 4 5 6
0 @ @ @ @ @ @ @
1 @ v < < < v @
2 @ v @ @ @ v <
3 S < < < < < @
4 @ ^ ^ @ ^ @ @
5 @ ^ ^ < ^ @ @
6 @ @ @ @ @ @ @```
This obviates the "mark that position as visited" step since that would erase this information and also doesn't seem to be necessary. Alternatively if you didn't want to mess up the original maze array you could use a secondary copy.

Anyway, to find the shortest path, begin at the goal and follow the arrows to the start.

3. Originally Posted by algorism
BFS is actually not that hard. The basic idea is to use a queue to hold the adjacent positions that you haven't visited yet. (Do you know how to make a queue?)

Initialize the queue with the start position and then enter a loop. If the queue becomes empty, no path was found. Otherwise, pop the front of the queue (initially the start position) and mark that position as visited. If that position is the goal position, success! Otherwise, push all that position's neighbors that haven't been visited yet onto the queue. Repeat the loop.

In order to find the shortest path once the goal position has been reached by the BFS, you need to save which position added each new position to the queue. One way to do that is to store symbols into the character array itself, which might end up looking something like this:
Code:
```` 0 1 2 3 4 5 6
0 @ @ @ @ @ @ @
1 @ v < < < v @
2 @ v @ @ @ v <
3 S < < < < < @
4 @ ^ ^ @ ^ @ @
5 @ ^ ^ < ^ @ @
6 @ @ @ @ @ @ @```
This obviates the "mark that position as visited" step since that would erase this information and also doesn't seem to be necessary. Alternatively if you didn't want to mess up the original maze array you could use a secondary copy.

Anyway, to find the shortest path, begin at the goal and follow the arrows to the start.
I'm..actually not too sure how I can go about doing that :/
I've already made a secondary copy of the maze via an arrCopy function. I think I understand the logic behind the BFS algorithm based on this website Maze Solver (shortest path finder) - CodeProject, but I have difficulty translating it into C. Especially on the part where we have to make this a sort of a loop and then somehow have the queue array correspond to the origin array in a lowest to highest order.

Do you mind guiding me along..? I know now that, if I have a 30-by-30 maze, I probably need an array that can hold the nodes for 900 cells, but since this node[900] is a 1d array, does that mean I should have a structure containing row and col, and insert that structure into each element to point to the corresponding cell for each node? Then, if my nodes[900] contains the position of the nodes, and I know that the node numbers from 1 to N corresponds to a position in the cell, my queue[900] and origin[900] would just need to hold the sequence of nodes (int) rather than the structure containing the position, am I right?

I removed the parts related to reading the input and the left-hand-rule for simplicity.
Code:
```#include <stdio.h>
#define SIZE 10

typedef struct{
int row, col;
} Pos;

void setNodes(Pos node[SIZE*SIZE]);

int main(void) {
char map[SIZE][SIZE+1]={{""}};
int n = SIZE, queue[SIZE*SIZE], origin[SIZE*SIZE], status[SIZE*SIZE];
Pos node[SIZE*SIZE]={0};

setNodes(node);

return 0;
}

void setNodes(Pos node[SIZE*SIZE]){
int row, col, cur=0;
for(row = 0; row < SIZE; row++){
for(col = 0; col < SIZE; col++){
node[cur].row = row;
node[cur].col = col;
cur++;
}
}
return;
}```

4. I think it can be simplified quite a bit from the link you give.
Either way, you'll need a queue.
Can you implement a queue that passes the following test?
Code:
```int main(void) {
Queue q;    // int front, back; Pos pos[QUEUE_SIZE]
qInit(&q);  // set front and back to 0

Pos a = {1, 2};  // Pos has row, col (in that order)
qPush(&q, &a);

Pos b = {5, 3};
qPush(&q, &b);

while (!qEmpty(&q)) {
Pos p;
qPop(&q, &p);
printf("%d, %d\n", p->row, p->col);
}

//qTerm(&q);  // if needed (dynamic allocation)
return 0;
}```