# Applicability of Dijkstra's algorithm to hypergraphs

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.

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
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?

• Hint: try to model your hypergraph as shortest-path equivalent graph. – Raphael Feb 6 '18 at 12:16
• @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? – UTF-8 Feb 6 '18 at 12:32
• I haven't worked through the details myself, but usually that is possible. – Raphael Feb 6 '18 at 12:38