Click here to Skip to main content
15,900,906 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
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);       

        while (q.Count() != 0)
            string j = q.Dequeue();
            foreach (string h in g.adjacentTo(j))
                if (!dist.ContainsKey(h))
                    dist.Add(h, 1 + dist[j]);

                if (j == p)
                    Console.WriteLine("               " + dist[j]);

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];
Updated 20-Dec-15 6:24am
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, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900