Finding all paths between two nodes in a graph Computer Science

---

Finding all paths between two nodes in a graph Posted: 01 Jan 2022 11:08 AM PST I'm learning graph theory and while I'm not quite confident I'm trying to use simple examples to get some practice in. Currently I'm trying to create a function that finds all simple paths between two vertices in a graph, but I'm not sure if my approach is correct. Let's say I have the following graph: Sorry, dark mode users! If I want to enumerate all the paths from A to D, I could start doing a DFS approach from A, advancing edge per edge until I hit D or until there are no more candidate nodes to visit. I could keep track of each edge's predecessor to enumerate the reverse list of edges that make up a single path. However, this only gives me one path, and so a pure DFS will ignore all other possible paths as soon as it finds one path that connects A to D. But if I assume that one or more paths can exist between nodes, then naturally I could count them and give them an index. I could say, for example, that the first path is [a, b, c] and the second path is [a, g] and so on. The longest simple path that I can think of in this example is [e, f, b, c]. So with these assumed indices, I could add a dictionary property to each edge that contains a path index as its key and the edge's predecessor in the path with the given index as its value. This way, I should be able to backtrack from D given its multitude of predecessors. I was wondering if this approach could work, and if it is actually correct for all graph types (i.e. directed, undirected, with or without cycles, multiple edges between nodes, etc.). I'll try to code a solution and create a gist but I'm not very confident I'll get it done any time soon. UPDATE: I wanted to try this approach with a dictionary of path indices, so I wrote code to count all the possible paths to populate an empty dictionary with the right keys, turns out this function already pretty much gives me the right sequence of nodes and edges, meaning I can also directly get all the paths from this function, which actually solves the problem I had in mind to begin with. submitted by /u/thejpguy [link] [comments]

You are subscribed to email updates from Computer Science: Theory and Application. To stop receiving these emails, you may unsubscribe now.	Email delivery powered by Google
Google, 1600 Amphitheatre Parkway, Mountain View, CA 94043, United States