About a graph algorithm! It is very diffcult , I think!
-
I need a method to find out All paths from a node( such as I) to another node (Such as J) in a digraph. the digraph is represented by adjacency matrix!
First off, you need to reduce the problem. You cannot necessarily determine all paths from I to J if there is a cycle in the graph, because there are (potentially) infinite paths. Detecting graph cycles is fairly simple. Search on Google for how. Now, if you are willing to reduce the problem to only Directed Acyclic Graphs, you simply start at I and traverse every possible path. The simplest implementation is to store a representation of the path (possibly just a list of vertex pointers). Every time you come to a point where you could traverse down two different edges, copy the list and traverse down both. (Of course, if there are more than two possible edges, make additional copies and traverse for each.) Since the graph is acyclic, the paths will either run into J (at which point they record/print themselves somewhere) or they will end unsuccessfully (at which point they do nothing else). This same logic (with minor modifications) will also work on cyclic graphs, but checking for cycles becomes necessary. e.g. Is vertex Q already in the path? If so, don't bother going there again, because it's a cycle. And of course, if there is actually a cycle in valid path (e.g. I->Q->Z->Q->J), it's impossible to return all the paths, because there really will be an infinite number of them. (e.g. I->Q->Z->Q->Z->Q->Z->...Q->J)