Graph: dijkstra/astar/bellmanFord/floydWarshall ignore reverse direction of undirected edges

[tyler-mitchell]

Summary

On Graph.undirected graphs, all four shortest-path algorithms — Graph.dijkstra, Graph.astar, Graph.bellmanFord, and Graph.floydWarshall — only traverse edges in their stored direction. A path that requires crossing an edge opposite to the direction it was passed to Graph.addEdge is not found. By contrast, Graph.connectedComponents and Graph.neighbors handle undirected edges correctly, so the modules disagree about reachability on the same graph.

Reproduction

Reproduced on effect@3.21.2 and effect@3.21.3 (latest at time of filing); the relevant code is unchanged on main.

import { Graph, Option } from "effect"

const g = Graph.undirected<string, number>((m) => {
  const a = Graph.addNode(m, "a")
  const b = Graph.addNode(m, "b")
  const c = Graph.addNode(m, "c")
  Graph.addEdge(m, a, b, 1)
  Graph.addEdge(m, c, b, 1) // stored direction c->b
})

console.log(Option.isSome(Graph.dijkstra(g, { cost: (e) => e, source: 0, target: 2 })))
// false — expected true (a-b-c is connected)
console.log(Option.isSome(Graph.astar(g, { cost: (e) => e, heuristic: () => 0, source: 0, target: 2 })))
// false — expected true
console.log(Option.isSome(Graph.bellmanFord(g, { cost: (e) => e, source: 0, target: 2 })))
// false — expected true
console.log(Graph.floydWarshall(g, (e) => e).distances.get(0)?.get(2))
// Infinity — expected 2
console.log(Graph.connectedComponents(g).length)
// 1 — correct: connectedComponents agrees the graph is connected

Reversing the second addEdge to Graph.addEdge(m, b, c, 1) makes all four algorithms succeed, confirming the result depends on edge storage direction, which should be irrelevant for an undirected graph.

Root cause

(line references against packages/effect/src/Graph.ts on current main)

addEdge does register an undirected edge in both endpoints' adjacency lists (the mutable.type === "undirected" branch, ~L1176). But:

• dijkstra (~L2406) and astar (~L2731) compute the neighbor as const neighbor = edge.target unconditionally. When the algorithm expands a node that is the stored target of an undirected edge, the computed "neighbor" is the node itself, so the edge is never crossed in the reverse direction. (In the repro, expanding b over the stored edge c->b relaxes b against itself instead of reaching c.)
• bellmanFord (~L2880) relaxes only edge.source -> edge.target regardless of graph kind.
• floydWarshall (~L2525) initializes the distance matrix only at dist[edge.source][edge.target].

Meanwhile connectedComponents and neighbors go through the getUndirectedNeighbors helper (~L2055), which correctly returns the other endpoint of each incident edge — hence the inconsistency.

Suggested fix

• In dijkstra/astar: when graph.type === "undirected", take the neighbor as the other endpoint (edge.source === currentNode ? edge.target : edge.source), as getUndirectedNeighbors does. (Self-loops need the same care getUndirectedNeighbors already takes after Graph.neighbors() returns self-loops in undirected graphs #5667.)
• In bellmanFord: also relax edge.target -> edge.source for undirected graphs. (Note any negative-weight undirected edge then constitutes a negative cycle, which matches the algorithm's semantics.)
• In floydWarshall: also initialize dist[edge.target][edge.source] (and the corresponding next/edgeMatrix entries) for undirected graphs.

Happy to provide more details if useful.

[fubhy]

Thanks for reporting. Here's the fixes:

• Fix undirected graph traversal effect-smol#2362
• Fix undirected graph traversal #6267