# UNDF: UNDF-2026-000000377
# dgraph-0001: CWE-407 O(P) route cycle-check inside hot BFS/Dijkstra neighbour loop

**Severity:** HIGH
**File:** `query/shortest.go`
**Function:** `runKShortestPaths` (line 286)
**Lines:** 56–63 (`indexOf`), 380 (call site)
**Repo:** https://github.com/dgraph-io/dgraph

## Description

`runKShortestPaths` implements Yen's k-shortest-paths algorithm using a priority
queue over `queueItem` nodes. Each `queueItem` carries a `route` — a slice of
`pathInfo` structs representing the path taken to reach the current node.

Inside the main dequeue loop (line 325) there is an inner `range` over all
neighbours (line 373). For each neighbour, the cycle-detection check at line 380
calls `item.path.indexOf(toUid)`:

```go
// query/shortest.go:380
if len(*item.path.route) > 0 && item.path.indexOf(toUid) != -1 {
    continue
}
```

`indexOf` is a linear scan of the path slice:

```go
// query/shortest.go:56–63
func (r *route) indexOf(uid uint64) int {
    for i, val := range *r.route {
        if val.uid == uid {
            return i
        }
    }
    return -1
}
```

## Complexity

| Symbol | Meaning |
|--------|---------|
| V | nodes (UIDs) in graph |
| E | edges (neighbours) explored |
| P | path length at dequeue time (up to V) |
| K | number of shortest paths requested |

Each dequeue processes up to E/V neighbours. Each neighbour call to `indexOf`
is O(P). In the worst case P → V. The total cost is:

```
O(K * V * (E/V) * V) = O(K * E * V)
```

For a dense graph (E ≈ V²) and large K this degrades to O(K * V³). Even for
sparse graphs (E ≈ V) it is O(K * V²), whereas the expected complexity of
Yen's algorithm with O(1) cycle detection is O(K * V * log V).

## Slow path

Every call to `indexOf` inside the neighbour loop is a full O(P) scan of the
current path slice. The path grows with each hop, so later queue items pay a
higher per-neighbour cost.

## Fast path

Replace the `*[]pathInfo` path representation with a `map[uint64]struct{}`
visited set carried alongside the route slice. `indexOf` (used only for cycle
detection) becomes an O(1) map lookup; path reconstruction continues to use the
slice for ordered output.

## Fix sketch

```go
type route struct {
    route       *[]pathInfo
    visited     map[uint64]struct{}   // NEW: uid → present
    totalWeight float64
}

// cycle check becomes:
if _, ok := item.path.visited[toUid]; ok {
    continue
}
```

When copying a route for a new branch, shallow-copy the visited map (one
allocation + N inserts where N = current path length — paid once per branch,
not per neighbour).

## Impact

Any Dgraph query using `shortest` with `numpaths > 1` on a graph with cycles
and long paths degrades from O(K * E * log V) to O(K * E * V). At V = 10,000
nodes and K = 10 paths this is a 10,000× slower cycle check per edge expansion.
Clients experience query timeouts on graphs that should complete in milliseconds.
