Thread: Shortest Path in Directed Hypergraphs with integer weights

Hi all,
i am fully stuck with this problem for days now.
Let me first show a brief introduction of what an hypergraph is, and then of course explain the problem.

Definition:
A Hypergraph H is a set of tuples <V, E, w> where V is a set of finite nodes, E is a set of hyperedges and w is a function which assigns each hyperedge an array of weights (which is actually a single integer weight that is shared among all edges coming out from the hyperedge(head nodes, (see below)), that's why it's an array)

In this case, the hypergraph has no cycles whatsoever

An hyperedge is a pair e = <T(e), h(e)>, where T(e) ⊂ V is the tail of the hyperedge and h(e) ⊂ V \ T(e), head of the hyperedge.

See attached image for examples.

Notes: In order to go through an hyperedge, one should previously be able to reach and mark each of the tail nodes of that hyperedge. See attached image to clearly understand.

Problem explanation: Find an algorithm, described in pseudo-code to the shortest path from source node S to destination node D.

Really, really thanks a lot to anyone who can help me!

I didn't quite understand the problem (I don't know what a hyperedge is), but what about Dijkstra's algorithm?

Dijkstra's algorithm is useful for digraphs where each node is connected to another node through a single weighted edge. In hypergraph this is not the case.

An hyperedge, is the box-style drawing in the picture I attached previously.

but to make it clearly, let n1 be tail node of an hyperedge H1, and n2, n3, n4 head nodes of an hyperedge H1. This means:

n1
|
H1 (weight = 1 as e.g.)
/ | \
n2 n3 n4

All single edges point downwards. This example can be read like: n1 is connected to n2, n3 and n4 by means of the hyperedge H1. The only obstacle is that to get through H1, you need to find a previous path to acquire n1 (none in this case cause n1 is the start point), meaning that in a bigger hypergraph, for sure there exist other hyperedges that got as head node n1.

Note: NP-Complete/Hard problem.

I think a program solving this problem would perform best if applying dynamic programming of some sort, but other methods would of course also solve the problem.

One solution using dynamic programming would be this:

Create a list, list a, of pairs consisting of a number (the total cost), and a vector containing Boolean values; one Boolean value for each node. The vectors represent states in the graph (which nodes have been visited and which have not), and the number is the minimum cost to get to that state. From the beginning, the list only contains one pair; 0 (the starting cost) and a vector containing only false at each element except from the element representing S.

Now, as long as you don't have any vector where the element representing D is true, do the following:

Create a new empty list, list b. For each pair in list a, consisting of a number n1, and a vector v1, representing state s1, consider each new state s2, that can be reached from s1, using only one move. Create a new vector v2, that represents s2, where all elements have the same value as in v1, except the element that represents the node differing between s2 and s1 (which should now be true), along with a number n2 = n1 + the cost to move from s1 to s2. If a pair in list b containing v2 has a number that is higher than n2, lower that number to n2. If no pair in list b contains v2, add a new pair to the list consisting of n2 and v2. When all pairs in list a have been looped through, replace it with list b, and if no pair's vector in the new list a has the element representing D set to true, start the cycle again.

When list a does contain a pair which vector's element representing D is set to true, the number in the pair will be the lowest cost to get from S to D. Note that this is only the cost of the shortest path; to get the actual shortest path, one could use backtracking from here, or one could save yet another element in each pair, representing the previous state, making the pairs triplets.

I'm sorry, I just realized you can't abort the search as fast as you have a list that contains a state where D has been reached. There is no guarantee that you won't find any path with lower cost if you continue to iterate (as in the case with Dijkstra's algorithm), so you will have to continue looping until you cannot reach any more state. With dynamic programming, the number of steps needed to reach the state will grow by each iteration, not necessarily the total cost; with Dijkstra's algorithm on the other hand, it is the opposite. When you do reach a state where D has been reached though, the total cost should be saved globally, unless a path with a lower cost has been found before.

Unfortunately, dynamic programming could prove impossible for this problem in reality, since the list size may grow exponentially as you iterate. Normal backtracking is probably better in this case, since it needs much less memory. When I used the word backtracking in my previous post, I didn't mean the method called backtracking which I linked to in this post, but some general term for recovering the path (this would require that the old list a is not deleted, but saved somewhere, maybe in yet another list).

Trikri, thanks a lot for your answer. Im going to test your idea in paper and see where i get! This problem is NP-Complete, so the complexity to resolve it is obviously exponentially either in time or space.

I just needed an exact solution for the shortest path, not the best-of-all times algorithm. Thanks a lot, i will reply soon with my results .