How to count all of the shortest paths between 2 vertices?

Question

So if I have two vertices 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 (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 compute the shortest path between 2 nodes but not the number of these shortest paths.

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;
                }
            }
        }
    }

It seems that where you currently do `return`, you could instead increment a counter, set to zero before the `while`, and then do the return with that counter value after the `while`, if the counter is greater than zero. — 500 - Internal Server Error, Dec 20 '15 at 17:29

score 0 · Answer 1 · answered Dec 20 '15 at 17:33

0

Before the foreach, init a variable int pathCount = 0;

Then, instead of the return; increment pathCount.

After the foreach, check if pathCount > 0 and if so, return it. Of course you have to change your return type to int.

answered Dec 20 '15 at 17:33

lex82

11,173
2
44
69

yo see my answer below – gen-y-s Dec 21 '15 at 07:22

gen-y-s · Accepted Answer · 2015-12-21T06:54:11.470

If a node u has x shortest paths, then an adjacent node v discovered thru it, would have x times y shortest paths, where y is the number of edges from u to v. Moreover, if v is reachable thru other adjacent nodes (with the same path length), then its count of shortest paths would be the sum of all the xy factors computed for each parent.

So the algorithm would be quite different than your prototype. I would suggest a main loop which increases the current length in each iteration, and then process the queue by looking at all the unvisited adjacent nodes of the nodes in the queue, computing the sum of xy factors for each of these adjacent nodes, and then clearing the queue and enqueing all the adjacent nodes (and marking them as visied) for the next iteration. In the first iteration the path length is 0 and the queue contains only the source node.

public void BFSDegree(Graph g, string s, string p)
{
    Queue<string> q = new Queue<string>();
    HashMap<string, int> path_counts = new HashMap<string, int>();
    path_counts.put(s, 1);       
    q.Enqueue(s);

    while (q.size()>0)
    {
        HashMap<string, int> adj_nodes = new HashMap<string, int>();
        foreach (string j in q) 
        {
            foreach (string h in g.adjacentTo(j))
            {
                if (!path_counts.ContainsKey(h))
                {
                    int count = 0;
                    if (adj_nodes.containsKey(h))
                        count=adj_nodes.get(h);
                    count += path_counts.get(j);
                    adj_nodes.put(h, count);
                }
            }
        }
        if (adj_nodes.containsKey(p))
        {
            Console.WriteLine("               " + adj_nodes.get(p));
            return;
        }
        path_counts.putAll(adj_nodes);
        q.clear();
        q.addAll(adj_nodes.keySet());
    }
}

Thank you! I have a question though I'm not familiar with HashMaps in c#, and I'm not sure if there exist a HashMap class in c#, I think this code is written in java? but I know it can be translated as class Dictionary in c# and I was able to translate all of the functions except for putAll function and addAll function, like is there an equivalent for them in the Dictionary class? — brokleyscoding, Dec 21 '15 at 18:33
Yeah, I used the Java collections in the code fragment I gave, but you can easily convert to C# - see here: http://stackoverflow.com/questions/3982448/adding-a-dictionary-to-another — gen-y-s, Dec 21 '15 at 19:13
For the Queue, you can also do the same thing (use a foreach loop to enqueue all the keys from adj_nodes). Please vote for this answer if you find it useful — gen-y-s, Dec 21 '15 at 19:16

How to count all of the shortest paths between 2 vertices?

2 Answers2