# k Shortest Paths between several nodes

• April 4th 2010, 04:22 AM
Quentin
k Shortest Paths between several nodes
Hello,

I'm a PhD student working in computational neuroscience, and more specifically, looking at efficient models for response to inject current onto dendritic trees. My current work has led me to something that I believe can be solved cleanly using graph theoretic approaches, though it's causing me a bit of a headache, having no background in this field whatsoever.

So, my problem :
I have a connected, weighted digraph that represents a neuronal dendritic tree. This should be a non-directed tree - however, I add in nodes x and y, where $x$ is where I inject current into the tree, and $y$ is where I measure it. My aim is to find all paths from $x$ to $y$ that are under some threshold in length ( sum of the weights on that path ). I understand there exists algorithms for this, so in itself, this causes no issues. The problem, however, gets more complicated.

I want to know what the voltage is in multiple places on the tree, and so have several nodes $y_i$. I also want to inject in multiple places, and so have several $x_i$ in the network. Each $x$ only has outbound edges and each $y$ only has inbound edges. So, what I need now, is all paths below some threshold in length, between all $x_i$ and $y_j$, $\forall$ $i$ and $j$.

As a further convolution, I need to connect several of these dendritic trees together, so we cannot guarantee that the graph we're looking at is indeed a tree, as it may well contain cycles.

Given that, in large graphs, the number of $x$ and $y$ should be much smaller than the number of other nodes, I was hoping to use this in some way to reduce the complexity of the graph by mapping it onto a bipartite graph, or even simply making it irreducible such that all unique paths ( paths with no repeat edges ) are found, and any repeat edges can be then added any number of times, until threshold is met. However, I believe that on large graphs, there will be a large number of such paths - will this cause a problem ? I'm hoping that the mostly-tree-like structure will keep this number from exploding.

The output I require is a list of paths, from all source to all target nodes, with the full path description. This is because I'm interested in the path length and which nodes are visited and how - the order in which they are visited leads to a different prefactor in my equation for voltage.

Any suggestions on this would be extremely appreciated, especially if you can educate me a little on what's possible, what I should be looking at, and how. I've considered things like Dijkstra, but that only gives me the single shortest path. I've looked at Eppstein's ( scarily complicated, for me ) "k shortest paths" algorithm, but that's single-source and single-target. I thought that, if I could reduce the problem to a bipartite graph, with all $x$ on one side and all $y$ on the other, we could build from there, building longer paths by adding edges that could repeat ( any non- $x$ and non- $y$ nodes have bidirectional edges, so can go back and forth between each other before advancing ), and this would allow us to generate a full path description.

This approach is still full of holes, however, and if anyone can offer a better suggestion, I'd be extremely grateful.

Apologies for a long post, and thank you for your time !

Quentin