CODEWITHSUNDEEP
algorithm
VoodooChild
VoodooChild

Reputation: 9784

graph algorithm question

How can I find all available path for each Vertices which won't cause a cycle? What algorithm to use? Please be brief and provide links if possible, and ask questions if something is not clear from the wonderful diagram below :) asdas

I am not looking for a shortest path or anything like that. Instead I just want to know which paths I can still draw on my graph without causing a loop/cycle. For example L4 can goto L1, L2, L5 AND L2 can goto L5...and so on....

I guess I want a Directed acyclic graph and need help finding out which algorithm to use and how?

Upvotes: 0

Views: 228

Answers (3)

Jander
Jander

Reputation: 5627

A shortest-path algorithm like Bellman-Ford or Dijkstra has the side effect of telling you which nodes you can reach from a given node "A" -- which is exactly the list of nodes from which edges to "A" would form a loop.

I suspect there is a way to modify Bellman-Ford to generate all these lists in one go, instead of running the algorithm separately for every node, but I'll leave that as an exercise for the reader. :)

Upvotes: 2

Amit S
Amit S

Reputation: 1083

Following is not the answer but just a way to think for this problem.
You can think for the problem from the opposite side. Find all the paths that have exactly one edge missing to form a cycle(I havn't think of it, how). Then those missing edges are not the edges you are looking. Accept everything other than that.

Upvotes: 1

ykatchou
ykatchou

Reputation: 3727

Look the Ford Algorithm

http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

Enjoy',

Upvotes: 1

Related Questions