How to make Shortest path in Grid using BFS in C#

Since I started in the university and learned about data structure. Queue was (I assume many of you know what Queue, it is a First- In-First-Out (FIFO) data structure) a very important data structure that is used in many algorithmic solutions. I used Java as programming language in the university.

When I ended university and started working for different business, I switch from Java and moved back to C# and Microsoft Stack in general. Since that time I have never used Queue, hence all solutions I worked with, typically used List or Dictionary.

I come with an old idea I have had in mind from university time, but never have had time to do it. The idea is how to make a visual representation of a simple shortest path in grid.

Playing with it over weekend, I found it motivating to write a short article about using Queue in C# to make a simple Breath First Search algorithm that uses Queue as shortest path in Grid.

So before I start, here would the final results looks like.

Example of how Short Path in Grid works using the Algorithm in this Article

Pre-requisites

You need to have basic knowledge about Queues, Stack, Graphs

About the article before we start

In this project, we will have 3 main parts of development, Creating Un weighted graph class, Creating Breath First Search Algorithm class and finally a presentation layer to visualize the Algorithm. This article is not about how Queue works, not about how BFS works or running time.. The article will focus on Breath First Search Algorithm implementation part only with basic features inspired from Algorithms fourth edition by Sedgewick and Wayne.

Let’s start

I have created an GraphUnweighted class with AddEdge and GetAdjacency method.

A Breath First Search algorithm need a graph that contains Vertices and Edges data, as well source Vertex where we start in path, and we will create another method that takes that target Vertex where we end our path, and gives all steps taken from source to target.

Now we know what we need, here next I create BreathFirstPath class with a constructor that takes the graph data and the source. And start Bfs searching method.

public BreathFirstPath(GraphUnweighted graphUnweighted, int source)
{
    _marked = new bool[graphUnweighted.CountVertex];
    _edgeTo = new int[graphUnweighted.CountVertex];
    _source = source;
    Bfs(graphUnweighted, source);
}

Here our Bfs Algorithm

private void Bfs(GraphUnweighted graphUnweighted, int source)
{
    Queue<int> queue = new Queue<int>();
    _marked[source] = true;
    queue.Enqueue(source);
    while (queue.Count > 0)
    {
        int v = queue.Dequeue();
        foreach (var w in graphUnweighted.GetAdjacency(v))
        {
            if (!_marked[w])
            {
                _edgeTo[w] = v;
                _marked[w] = true;
                queue.Enqueue(w);
            }
        }
    }
}

We will have 2 basic feature in our class, HasPathTo and PathTo:

public bool HasPathTo(int v)
{
    return _marked.ElementAtOrDefault(v);
}
public IEnumerable<int> PathTo(int v)
{
    Stack<int> stack = new Stack<int>();
if (HasPathTo(v))
    {
        for (int i = v; i != _source; i = _edgeTo[i])
        {
            stack.Push(i);
        }
        stack.Push(_source);
    }
return stack;
}

The key of PathTo is to create a list of all Vertices between source and target that we take and make visual representation of in our project.

Now before moving to presentation layer, lets make a test to out BFS algorithm.

Lets in our main method, try creating a Undirected and Unweighted Graph with 7 Vertices and 6 edges.

In following code we gone create our graph with 7 vertices based on in figure above, where add edge defines the connection between vertices:

GraphUnweighted graph = new GraphUnweighted(7);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(0, 3);
graph.AddEdge(1, 4);
graph.AddEdge(2, 5);
graph.AddEdge(3, 6);

Now we have our graph, lets run the algorithm to get some calculations:

Console.WriteLine($"Number of edges {graph.CountEdge}");
Console.WriteLine($"Number of vertices {graph.CountVertex}");
Console.WriteLine();
int source = 0;
int target = 6;
var adjacency = graph.GetAdjacency(source);
Console.WriteLine($"source vertex {source} is connected to target vertices: {string.Join(" - ", adjacency)}");
var bfs = new BreadthFirstPath(graph, source);
Console.WriteLine($"source vertex {source} is connected to target vertex {target}: {bfs.HasPathToo(target)}");
Console.WriteLine($"source vertex {source} is has path to target vertex {target} via: {string.Join(" -> ", bfs.PathTo(target))}");

The output of above console code will be like this:

Number of edges 6
Number of vertices 7
source vertex 0 is connected to target vertices: 3 - 2 - 1
source vertex 0 is connected to target vertex 6: True
source vertex 0 is has path to target vertex 6 via: 0 -> 3 -> 6

As we can see, one important result is the last line, it telling us that there are a connection between vertex 0 and 6 via 0->3->6.

It will be time consuming to maintain AddEdge manually for bigger map. Therefore I have created a small map to test my code with Vertices label numbers, where all place -1 means blocked area, and all positive integers are connected to vertical or horizontal neighbor, there is no rules how you should achieve this, it is just an example:

00;01;02;03;04;05;06;07;08;-1
10;11;12;13;14;15;16;17;18;-1
20;21;22;23;24;25;26;27;28;-1
-1;-1;-1;-1;-1;-1;-1;-1;-1;-1

And I will run the same Algorithm in console, this time the target is 28.

And I will get following results:

Number of edges 42
Number of vertices 40
source vertex 0 is connected to target vertices: 10 - 1
source vertex 0 is connected to target vertex 28: True
source vertex 0 has path to target vertex 28 via: 0 -> 10 -> 20 -> 21 -> 22 -> 23 -> 24 -> 25 -> 26 -> 27 -> 28

Now with all that learning and POC, here after I created an ASP.NET Razor project, where I made a bigger map, and let the user by clicking mouse to pick a source and target in grid. And here is the final result:

That is it. you are welcome to play with the UI on this link.

The Graph and UI code is not provided here, but it is left to you to play with it. If you think I should share the code, please comment.

Conclusion

As you can see, algorithm are very powerful to solve simple and complicated problems. In our case using the right data structure and few lines of code, we was able to achieve a very fast algorithm to find a path in grid. This path and grid could be bigger grid or representation of bigger map or route etc. that takes long time for human to calculate. Of course there are other types of shortest path algorithms designed for different purpose, but conceptually they are almost the same. For this grid it is also possible to solve this shortest path using Dynamic Programming Algorithm as well, I might find some time in future to make another article about it. In this post I wanted to demonstrate how BFS shortest path can be visualized in User Interface. So you are welcome to take the code make your own presentation layer (UI) 😜.

Originally published at https://itbackyard.com on February 2, 2022.