14. k-shortest - the top K routes, cheapest first

what this does

k-shortest returns up to k loop-free routes between two nodes, cheapest first, with the node sequence and the cost of each. Where dijkstra gives you a single number, this gives you the routes themselves and their runners-up. GET /v1/tenants/:t/graph/:schema/k-shortest takes rel, source, target and k.

when to use it

• Presenting alternatives - the best route plus the next few, so a person can choose.
• Failover planning. If the cheapest path breaks, what is the second cheapest, and does it depend on the same intermediate node?
• Explaining a connection. "Here are the three ways A reaches B" is a much better answer than a single cost.

schema requirement

The relation must be declared in the schema's [[relations]] block. If you pass weight_col, the relation's target table must also declare that column. See schemas/reference#relations.

the request

This endpoint names its endpoints source and target, not src and dst the way path, dijkstra and all_simple_paths do. k is required and is capped at 50; asking for more is a 400 rather than a silent truncation. By default every edge weighs 1, so the ranking is by hop count - pass weight_col to read each edge's weight from a named column on the destination row instead.

curl -G "https://$OC_HOST/v1/tenants/$OC_TENANT/graph/social.users/k-shortest" \
  --data-urlencode "rel=follows" \
  --data-urlencode "source=alice" \
  --data-urlencode "target=erin" \
  --data-urlencode "k=3" \
  -H "Authorization: Bearer $OC_TOKEN"

paths = db.graph.k_shortest(
    "social.users",
    src="alice",      # sent as the `source` query parameter
    target="erin",
    rel="follows",
    k=3,
)
for p in paths:
    print(p.nodes, p.cost)

// The TypeScript SDK does not wrap the graph algorithms - use fetch.
const qs = new URLSearchParams({
  rel: "follows",
  source: "alice",
  target: "erin",
  k: "3",
});
const res = await fetch(
  `https://${OC_HOST}/v1/tenants/${OC_TENANT}/graph/social.users/k-shortest?${qs}`,
  { headers: { Authorization: `Bearer ${OC_TOKEN}` } },
);
const { paths } = await res.json();

// The Go SDK does not wrap the graph algorithms - use net/http.
url := "https://" + OC_HOST + "/v1/tenants/" + OC_TENANT +
    "/graph/social.users/k-shortest?rel=follows&source=alice&target=erin&k=3"

req, _ := http.NewRequestWithContext(ctx, "GET", url, nil)
req.Header.Set("Authorization", "Bearer "+OC_TOKEN)

resp, _ := http.DefaultClient.Do(req)
defer resp.Body.Close()

var out struct {
    Paths []struct {
        Nodes []string `json:"nodes"`
        Cost  float64  `json:"cost"`
    } `json:"paths"`
}
json.NewDecoder(resp.Body).Decode(&out)

what you get back

{
  "paths": [
    { "nodes": ["alice", "carol", "dave", "erin"], "cost": 3.0 },
    { "nodes": ["alice", "bob", "carol", "dave", "erin"], "cost": 4.0 }
  ]
}

An object with a paths array, one entry per route, ascending by cost. nodes is the walk in order as plain strings, including both endpoints. Fewer than k entries simply means the graph has no more loop-free routes. An unreachable target is a 200 with "paths": [], not a 404, and a source equal to target comes back as a single zero-cost path.

how it works

• Yen's algorithm finds the shortest path, then repeatedly forces a deviation at each node along it and keeps the cheapest result it has not already emitted.
• Routes are loop-free by construction: no node repeats inside a single path.
• With no weight_col every edge weighs 1, so the ranking is by hop count and matches what a breadth-first search would find.
• With weight_col set, each edge's weight is read from that column on the destination row and coerced to a float. The relation has to exist on the schema for that lookup, and an unknown relation name is a 400.
• k above 50 is rejected with the ceiling quoted in the message, so callers learn to budget instead of silently receiving a truncated list.