Finding All Possible Paths in a Directed Graph

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

Discussion Overview

The discussion revolves around finding all possible paths from a given node in a directed graph. Participants explore definitions, methods for counting paths, and the complexity of different types of graphs.

Discussion Character

  • Exploratory
  • Conceptual clarification
  • Debate/contested

Main Points Raised

  • One participant asks how to find all possible paths from a node in a directed graph.
  • Another participant expresses confusion about the terms "node" and "directed graph," seeking a clearer explanation.
  • A third participant defines a node as a location, using the analogy of cities on a map to illustrate the concept.
  • One participant suggests counting paths individually as a method, while also noting the potential complexity of certain graphs.
  • Another participant mentions the possibility of applying a theorem or formula specific to the graph in question.

Areas of Agreement / Disagreement

There is no consensus on the methods for finding paths, as participants express varying levels of understanding and propose different approaches.

Contextual Notes

Some participants may lack foundational knowledge of graph theory, which could limit their ability to engage with the topic effectively. The complexity of certain graphs, such as those representing phone systems or the internet, is acknowledged but not fully explored.

Who May Find This Useful

This discussion may be useful for individuals interested in graph theory, computer science, or those seeking to understand pathfinding algorithms in directed graphs.

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