Home
> Uncategorized > Determine whether there exists a path in graph G of length L.

## Determine whether there exists a path in graph G of length L.

Determine whether there exists a path in graph G of length L.

Solution:

If the graph has a cycle, then the graph has a path of any length L.

If the graph does not have a cycle , then we are finding a simple path of length L.

We will use DFS with some modification to find simple path of length L.

For this with every node n, we will maintain a value named maxPath (other than start_time and end_time) which determines path of Maximum value.

We will initialize each nodes of G with maxPath = 0;

So, the steps to find simple path of Lengh L is :

1. Run modified DFS-visit()

2. check each node for the maxPath value.

DFS-visit(u) { time = time + 1 u.start = time; for each v <em>belongs-to</em> adj[u] if ( v.color = WHITE ) { DFS-visit(v) if (u.maxPath < v.maxPath + 1 ) u.maxPath = v.maxPath + 1; } u.endtime = time + 1; u.color = BLACK

Advertisements

Categories: Uncategorized

Thank you so much .. that was very helpful

I have the qualifying exam tomorrow 🙂

“If the graph has a cycle, then the graph has a path of any length L”

Huh? I have one node A with one edge (A,A) with weight of 5. I can have paths like 0, 5, 10, 15 length, but can I have e.g. path of 3 length? I don’t think so…