Number of walks from source to sink with exactly h hops

user_1826912 0
Viewed 181

Given an un-directed graph, a starting vertex and ending vertex. Find the number of walks (so a vertex can be visited more than once) from the source to the sink that involve exactly h hops. For example, if the graph is a triangle, the number of such paths with h hops is given by the h-th Jakobstahl number. This can be extended to a fully connected k-node graph, producing the recurrence (and closed form solution) here.

When the graph is an n-sided polygon, the accepted answer here expresses the number of walks as a sum of binomial terms.

I assume there might be an efficient algorithm for finding this number for any given graph? We can assume the graph is provided in adjacency matrix or adjacency list or any other convenient notation.

breadth-first-search graph big-o algorithm
3 Answers

If you take the adjacency matrix of a graph and raise it to the nth power, the resulting matrix counts the number of paths from each node to each other that uses exactly n edges. That would provide one way of computing the number you want - plus many others you aren’t all that interested in. :-)

Assuming the number of paths is “small” (say, something that fits into a 64-bit integer), you could use exponentiation by squaring to compute the matrix in O(log n) multiplies for a total cost of O(|V|ω log n), where ω is the exponent of the fastest matrix multiplication algorithm. However, if the quantity you’re looking for doesn’t fit into a machine word, then the cost of this approach will depend on how big the answer is as the multiplies will take variable amounts of time. For most graphs and small n this won’t be an issue, but if n is large and there are other parts of the graph that are densely connected this will slow down a bit.

Hope this helps!

user_5015570

A solution to this would be to use a modified BFS with two alternating queues and a per-node counter for paths to this node of a certain length:

paths(start, end, n):
    q = set(start)
    q_next = set()
    path_ct = map()
    path_ct_next = map()

    path_ct[start] = 1

    for i in [0, n):  # counting loop
        for node in q:  # queue loop
            for a in adjacent(node):  # neighbor-loop
                path_ct_next[a] += path_ct[node]
                q_next.add(a)

        q = q_next
        q_next = set()

        path_ct = path_ct_next
        path_ct_next = map()

   return path_ct_next[end]

The basic assumption here is that map() produces a dictionary that returns zero, if the entry doesn't yet exist. Otherwise it returns the previously set value. The counting-loop simply takes care of doing exactly as many iterations as hops as required. The queue loop iterates over all nodes that can be reached using exactly i hops. In the neighbor-loop finally all nodes that can be reached in i + 1 hops are found. In this loop the adjacent nodes will be stored into a queue for the next iteration of counting-loop. The number of possible paths to reach such a node is the sum of the number of paths to reach it's predecessors. Once this is done for each node of the current iteration of counting-loop, the queues and tables are swapped/replaced by empty instances and the algorithm can start over.

user_46686060

You can make an algorithm that keep searching all possible paths , but with a variable that will contain your number of hops

For each possible path , each hop will decrement that variable and when arriving to zero your algorithm goes to trying another path , and if ever a path arrives to the target before making variable reachs zero , this path will be added to the list of your desired paths

user_98528700
Related