Click here to Skip to main content
14,666,479 members
Rate this:
Please Sign up or sign in to vote.
See more:
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];
       }
Posted
Updated 20-Dec-15 6:24am
v2
Comments
BillWoodruff 20-Dec-15 12:00pm
   
I believe for anyone to help you with this, you are going to need to show the code for your 'adjacent method ... unless you are lucky and someone comes along familiar with BFS.
Member 12160712 20-Dec-15 12:25pm
   
Check the edit :)

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100