Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.


share|cite|improve this question
"the shortest path" would be a path of length one. But perhaps there are some conditions you have omitted. – Gerry Myerson Aug 24 '11 at 0:34
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:'s_algorithm – Ragib Zaman Aug 24 '11 at 0:36
@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. – Gerry Myerson Aug 24 '11 at 3:38
@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? – graphtheory92 Aug 24 '11 at 10:27
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? – Gerry Myerson Aug 25 '11 at 4:59

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.