Ask a graph theory algorithm

wangyanping

In an undirected graph, given two points u and v, and there are no edges between u and v, find the number of simple paths that do not intersect between these two points?

aog777ys

Network streaming

菜鸟级高手

I think it ’s easy to use breadth search

wangyanping

菜鸟级高手: I have also considered breadth search, but there is no better way to solve the two constraints of "disjoint" and optimization? Can you say something specific?

菜鸟级高手

Each time an element is traversed, a mark is added. It is no longer accessed before the mark is cleared, which can avoid "intersection"
 What do you mean by optimization?

wangyanping

Optimization refers to that the number of the last disjoint paths is the largest.

If you follow your method, the complexity of the algorithm is very high

cocosex

Maximum flow

dommionr

If this problem is solved well, then
The google topic is simple

May I ask whether there is a path (it can be repeated) that passes through K-1 nodes between u and v.

dommionr

Friends who think using network streaming, what do you think?

wangyanping

bigc: Is there a path through K-1 nodes between u and v: Google's questions can be calculated by matrix operations, and by the method of passing closure