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$
  • $\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

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.