CODEWITHSUNDEEP
algorithmgraphgraph-algorithm
biswas N
biswas N

Reputation: 381

Number of Paths in a Graph

I have an undirected, unweighted graph. Let us fix a vertex and find all distinct paths from that vertex which covers all vertices of the graph. The task is to find the number of possible such paths from every vertices.
Eg: Let us take a graph of 4 vertices [ 1, 2, 3, 4]. And the edges are (1,2), (2,3), (3,4), (4,2). Here answer is 4. The paths are 1>2>3>4, 1>2>4>3, 3>4>2>1, 4>3>2>1.

I have come with an algorithm which uses brute-force technique to find the number of possible such paths, initialized by each vertex.
Eg: For the above example:
From vertex 1 there is 2 such path;
From vertex 2 there is no such path;
From vertex 3 there is 1 such path;
From vertex 4 there is 1 such path;
So the answer is 2+1+1=4.

Is it possible to solve this problem in a better time complexity?

Upvotes: 0

Views: 429

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65506

There's an O(2^n n^2)-time algorithm obtained by modifying the Held--Karp DP. The idea is, for each subset S of vertices paired with some endpoint t in S, compute the number of paths that visit exactly the vertices in S and end at t by summing, for each neighbor u of t that is in S, the count for visiting S - {t} and ending at u. As a base case, the singleton sets all have count 1. In Python 3:

import itertools
def count_hamilton_paths(graph):  # graph is a dict of adjacency lists
    vertices = frozenset(graph)
    table = {(frozenset({t}), t): 1 for t in vertices}
    for r in range(2, len(vertices) + 1):
        for subset_tuple in itertools.combinations(vertices, r):
            subset = frozenset(subset_tuple)
            for t in subset:
                subset_minus_t = subset - frozenset({t})
                table[(subset, t)] = sum(table[(subset_minus_t, u)]
                                         for u in graph[t]
                                         if u in subset_minus_t)
    return sum(table[(vertices, t)] for t in vertices)

print(count_hamilton_paths({1: {2}, 2: {1, 3, 4}, 3: {2, 4}, 4: {2, 3}}))

Upvotes: 1

Related Questions