Question

Hi,

first of all I want to mention, that I'm pretty new to graph-theory. Currently I'm about to write a path search algorithm and I want to take advantage of previous knowledge.

So this is the setup: -the graph is fully connected

-the graph is directed

-number of states are given

-number of edges are given

-the graph displays a markovchain, so all outgoing edges of a node have to be 1, summed up

-there is one input node and one output node, no more absorbing states

before the algorithm starts i want to estimate the probability of the most probable path.

I was thinking about: what is the most probable graph structure, what would be the average connectivity and how would the probability distribution be.

like I said before I'm new to this, so this might be stupid or to easy or impossible :P

Answer 1

My just published book , " A New Algorithm for Studying Routes in a Connected Graph', Kindle Edition, by Amazon. Com may be helpful in your problem. My new algorithm does not employ search, recursion or AI. It is based on combinatorial Analysis/Block Design. My algorithm produces all routes of length (PL) between the starting node, s and all other nodes. The number of such routes is simply Avg(Nc)^PL where Avg(Nc) is average degree of nodal connectivity. My software package (EcoNets) also selects routes (simple or cyclic) between any two nodes s and t. It can also select any routes with any set of route-attributes such as distance, link costs or reliabilities. A sample network (10n, 20s) took about 1 minute of my laptop and about 1 Gigabytes of RAM for all routes with PL <=10. If you go to Amazon.com website, you can peruse the sample pages of my book and study the algorithm. Wish you luck.