0
$\begingroup$

When I search for Dijkstra's algorithm and hypergraphs, I don't get any results discussing it. The Wikipedia page regarding Dijkstra's algorithm doesn't mention hypergraphs and the one regarding hypergraphs doesn't mention Dijkstra's algorithm. When I search for shortest path algorithms for hypergraphs, I only get results with complicated algorithms.

But when I look at Dijkstra's algorithm, I can't seem to see anything in it where it uses the fact that each edge only connects two nodes.

Wikipedia states this pseudocode:

1  function Dijkstra(Graph, source):
2      dist[source] ← 0                                    // Initialization
3
4      create vertex set Q
5
6      for each vertex v in Graph:           
7          if v ≠ source
8              dist[v] ← INFINITY                          // Unknown distance from source to v
9              prev[v] ← UNDEFINED                         // Predecessor of v
10
11         Q.add_with_priority(v, dist[v])
12
13
14     while Q is not empty:                              // The main loop
15         u ← Q.extract_min()                            // Remove and return best vertex
16         for each neighbor v of u:                      // only v that is still in Q
17             alt ← dist[u] + length(u, v) 
18             if alt < dist[v]
19                 dist[v] ← alt
20                 prev[v] ← u
21                 Q.decrease_priority(v, alt)
22
23     return dist, prev

The only time this algorithm mentions connections is in line 16, where it says "for each neighbor v of u".

Could I simply use this algorithm for hypergraphs and only get correct results?

$\endgroup$
4
  • $\begingroup$ Hint: try to model your hypergraph as shortest-path equivalent graph. $\endgroup$ – Raphael Feb 6 '18 at 12:16
  • $\begingroup$ @Raphael I know that I can simply transform my hypergraph into a regular graph where each hyperedge is a clique. So you're saying I can just do the same thing implicitly? $\endgroup$ – UTF-8 Feb 6 '18 at 12:32
  • $\begingroup$ I haven't worked through the details myself, but usually that is possible. $\endgroup$ – Raphael Feb 6 '18 at 12:38
  • $\begingroup$ I believe that finding the shortest hyper path is NP-hard for general hyper-graphs. However, for certain cases you can find efficient algorithms. Look at Liang Huang 2008, Gallo et al. 1993 and Nielsen et al. 2005. A hyperpath is fundamentally different than a "regular" path in a regular graph. So regarding your question of just replacing the hyperedges with cliques, depends on what you want. In a shortest hyperpath, you usually want entire hyperedges in the solution which is not equivalent to what you get in the clique version. $\endgroup$ – DariusTheGreat Jan 4 at 9:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.