# UNDF: UNDF-2026-000000467
# neo4j-0001: Dijkstra predecessors List.contains() — O(E×P) in all-shortest-paths mode

## Severity
MEDIUM

## Location
`community/graph-algo/src/main/java/org/neo4j/graphalgo/impl/shortestpath/Dijkstra.java`
Line 324

## Description
When `calculateAllShortestPaths` is true, the Dijkstra edge-expansion loop calls
`myPredecessors.contains(relationship)` to guard against adding a duplicate
predecessor edge.  `predecessors1` and `predecessors2` are both declared as
`Map<Node, List<Relationship>>` (lines 101-102), so each `contains()` call is an
O(P) linear scan of the predecessor list for that node.

The call site is inside the per-relationship inner loop (iterating every edge
leaving `currentNode`), so the total cost for a node with degree D and P
predecessor entries is O(D × P).  Over the full graph traversal this becomes
O(E × P_max) where E is the number of edges examined and P_max is the maximum
predecessor-list length at any single node.

In dense graphs with many shortest paths through high-degree hub nodes this
degrades to O(E²) in the worst case.

## Defective Code
```java
// Dijkstra.java:101-102
protected Map<Node, List<Relationship>> predecessors1 = new HashMap<>();
protected Map<Node, List<Relationship>> predecessors2 = new HashMap<>();

// Dijkstra.java:321-324  (inside per-relationship loop)
List<Relationship> myPredecessors = predecessors.get(currentNode);
// Dont do it if this relation is already in predecessors (other direction)
if (myPredecessors == null || !myPredecessors.contains(relationship)) {
```

## Root Cause
`List<Relationship>` uses `ArrayList.contains()` which is O(N) linear scan.
The guard is inside the inner relationship-iteration loop, making each node
expansion O(D × P) instead of O(D).

## Fix
Replace `List<Relationship>` with `Set<Relationship>` (e.g. `LinkedHashSet` to
preserve insertion order if callers rely on it):

```java
protected Map<Node, Set<Relationship>> predecessors1 = new HashMap<>();
protected Map<Node, Set<Relationship>> predecessors2 = new HashMap<>();
```

Then the `contains()` check at line 324 becomes O(1) and the `predList.add()`
at line 331 and 364 naturally deduplicates via `Set.add()` semantics, so the
explicit `contains()` guard can be removed entirely:

```java
// before (line 324-333):
if (myPredecessors == null || !myPredecessors.contains(relationship)) {
    Set<Relationship> predList = predecessors.get(target);
    if (predList == null) {
        // bogus: back to start node
    } else {
        predList.add(relationship);
    }
}

// after:
Set<Relationship> predList = predecessors.get(target);
if (predList != null) {
    predList.add(relationship);   // Set.add() is idempotent
}
```

Similarly update `predecessors.put(target, predList)` sites to create a
`LinkedHashSet` instead of `LinkedList`.

## Complexity
| Mode | Before | After |
|------|--------|-------|
| Single shortest path | O(m + n log n) | O(m + n log n) (unchanged) |
| All shortest paths | O(E × P_max) | O(E) |
