1 Attachment(s)

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!