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

Example of how Short Path in Grid works using the Algorithm in this Article
public BreathFirstPath(GraphUnweighted graphUnweighted, int source)
{
_marked = new bool[graphUnweighted.CountVertex];
_edgeTo = new int[graphUnweighted.CountVertex];
_source = source;
Bfs(graphUnweighted, source);
}
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);
}
}
}
}
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;
}
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);
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))}");
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
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
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

Conclusion

--

--

Maytham is a passionate software developer with more than ten years of experience. His motivation is to help transform ideas into production ready systems.

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Maytham Fahmi

Maytham Fahmi

Maytham is a passionate software developer with more than ten years of experience. His motivation is to help transform ideas into production ready systems.