So if I have two nodes in a graph, and they are connected through more than one edge while having the same shortest path between them (i.e if I have node A and node B and they are connected directly through three edges : edge 1, edge 2, edge 7 (there are 3 shortest paths between them each of distance 1) so the count should return 3) How can I modify the BFS algorithm to achieve that? This is my code, it only computes the shortest path between 2 nodes (i.e shortest path between node A and node B = a distance of 1) but not the number of these shortest paths.
Dictionary <string, int> dist = new Dictionary <string, int>();
public void BFSDegree(Graph g, string s, string p)
{
Queue<string> q = new Queue<string>();
dist.Add(s, 0);
q.Enqueue(s);
while (q.Count() != 0)
{
string j = q.Dequeue();
foreach (string h in g.adjacentTo(j))
{
if (!dist.ContainsKey(h))
{
q.Enqueue(h);
dist.Add(h, 1 + dist[j]);
}
if (j == p)
{
Console.WriteLine(" " + dist[j]);
return;
}
}
}
}
edit: This is the adjacent function, although I don't think it can be understood without posting the whole graph class, so I can post the whole class if you want.
Dictionary <string, Hashset<string>> dic = new Dictionary <string, Hashset<string>> ();
public IEnumerable<string> adjacentTo(string v)
{
return dic[v];
}