graph algorithm question

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?

No it is not homework. Just haven't used any of the algorithm for a while and have a need to use one now. So I thought what better place to learn than the wonderful SO :) — VoodooChild
– VoodooChild, Commented Oct 15, 2010 at 7:23
@Amit S: You would draw a line from L4 to L5 with the arrow pointing at L5 :) — VoodooChild
– VoodooChild, Commented Oct 15, 2010 at 7:26
@Amit S: No big deal, I thought maybe I might have made an error in my question. — VoodooChild
– VoodooChild, Commented Oct 15, 2010 at 7:33

Jander · Accepted Answer · 2010-10-15 07:45:29Z

2

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. :)

answered Oct 15, 2010 at 7:45

Jander

5,7171 gold badge26 silver badges21 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

ykatchou · Accepted Answer · 2010-10-15 07:19:35Z

1

Look the Ford Algorithm

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

Enjoy',

answered Oct 15, 2010 at 7:19

ykatchou

3,7471 gold badge25 silver badges27 bronze badges

Comments

Amit S · Accepted Answer · 2010-10-15 07:33:41Z

1

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.

answered Oct 15, 2010 at 7:33

Amit S

1,0832 gold badges9 silver badges18 bronze badges

Collectives™ on Stack Overflow

graph algorithm question

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest