Finding All Possible Paths in a Directed Graph

  • Context: Undergrad 
  • Thread starter Thread starter Topple
  • Start date Start date
Click For Summary
SUMMARY

This discussion focuses on finding all possible paths from a given node in a directed graph. A node is defined as a location, analogous to cities on a map, where each city represents a node that can be traveled into and away from. The conversation highlights two methods for pathfinding: manually counting paths one by one, which can be tedious, and applying specific theorems or formulas relevant to the graph type. The complexity of certain graphs, such as phone systems or the internet, is also acknowledged.

PREREQUISITES
  • Understanding of directed graphs and their properties
  • Familiarity with graph theory terminology
  • Basic knowledge of algorithms for pathfinding
  • Experience with mathematical theorems applicable to graphs
NEXT STEPS
  • Research algorithms for finding paths in directed graphs, such as Depth-First Search (DFS)
  • Learn about specific theorems in graph theory, like the Bellman-Ford theorem
  • Explore graph visualization tools to better understand node connections
  • Study applications of directed graphs in real-world scenarios, such as network routing
USEFUL FOR

Students, computer scientists, and software developers interested in graph theory, algorithm design, and applications of directed graphs in various fields.

Topple
Messages
1
Reaction score
0
Do you know how to get all the possible paths from a given node in a directed graph?
Thanks a lot
 
Mathematics news on Phys.org
i don't actually know what a node or a directed graph is :( is it that I am too stupid or are you being more general than would be expected? idk but for my benefit could you explain it a bit more clearly? thanks
 
A node is a location. For example, if you were planning a trip, you would of course establish a path that would get you to your destination fastest. On a map, each city would represent a node that you may travel into and away from.
 
Your question is too general, but I'll give you a tip -

a) Try counting these paths one by one, which may be tedious.

b) If you have some type of thoerem or formula which applies to this specific graph then use the formula.

Some graphs are extremely complex - like phone systems or the internet for eg.
 

Similar threads

Undergrad Traffic simulation : directed graph including specific rules
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Find Smallest Subtree of G w/ Nodes from S
  • · Replies 5 ·
Replies
5
Views
2K
Undergrad Edge connectivity of a graph given the number of edge disjoint paths
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Find Two Equal Length Paths in a Tree Graph
  • · Replies 4 ·
Replies
4
Views
2K
Comp Sci Using Single Source Shortest Path Algorithm to find the longest path
  • · Replies 4 ·
Replies
4
Views
2K
Undergrad Question regarding degrees of a graph and its biconnected components
  • · Replies 34 ·
2
Replies
34
Views
5K
MHB How to check if search problem has no solution in depth limit search?
  • · Replies 1 ·
Replies
1
Views
1K
How to check if search problem has no solution in depth limit search?
  • · Replies 2 ·
Replies
2
Views
2K
Undergrad Finding if a subgraph of a minimal non-planar graph is maximal planar
  • · Replies 1 ·
Replies
1
Views
2K
High School Proof Pertaining to Possible Paths Through 3 Dimensions
  • · Replies 18 ·
Replies
18
Views
3K