1
$\begingroup$

Is it possible to predict the edges of the shortest path (or number of walks) having data such as density, average degree of nodes, degree of each node, number of nodes and number of edges? or do I need more data?

Mathematically (without use of computer) I cannot count each time the shortest path, (can I?), so the only thing I need is to know how many steps, or edges I have to go through.

Thanks!

  • 0
    "the shortest path" would be a path of length one. But perhaps there are some conditions you have omitted.2011-08-24
  • 0
    Are you looking to count the number of minimal walks between a given two points, or simply to predict the path of a single minimal walk? There exists algorithims to find a minimal walk, called Dijkstra's algorithm: http://en.wikipedia.org/wiki/Dijkstra's_algorithm2011-08-24
  • 0
    @Ragib, Dijkstra's algorithm requires you to know all the edges. Nicola's question is unclear, but I think it's asking whether you can do anything if you know a lot less about the graph, say, just the degree of each vertex.2011-08-24
  • 0
    @Gerry got my question. I know I can use Djkstra, but since it is an computational algorithm it means I need a computer. I would like to predict mathematically (just with linear formulas) the all-pairs shortest path length, or the shortest path from a given point. Can I?2011-08-24
  • 0
    The question is still unclear. "the shortest path from a given point" is a path of length 1 from that point to any neighboring point. What do you really mean?2011-08-25
  • 0
    Let's consider a graph G(v,e), what's the shortest path (this path will be same as the minimum spanning three) from a point v to touch all the other vertices ?2011-08-25
  • 0
    The question is still unclear. A path is not (in general) the same as a spanning tree. Also, a minimum spanning tree only makes sense in the context of weighted graphs, but you have not indicated that you are talking about weighted graphs. Are you? My advice would be to rewrite the question so it asks what you actually want to ask, unambiguously.2011-08-25
  • 0
    @Gerry I think Nicola is looking for the diameter of his graph. Nicola, could you check [this wikipedia article](http://en.wikipedia.org/wiki/Distance_(graph_theory)) and tell us if diameter is what you are looking for and then refine your question to reflect this.2011-08-25

0 Answers 0