k_shortest_paths: Find K Shortest Loopless Paths (Yen's Algorithm)

In cograph: Analysis and Visualization of Complex Networks

Find K Shortest Loopless Paths (Yen's Algorithm)

Description

Computes up to k shortest loopless paths between two nodes using Yen's algorithm. Each path is a sequence of distinct nodes from source to target.

Usage

k_shortest_paths(x, from, to, k = 3, weights = NULL, directed = NULL, ...)

Arguments

x	Network input: matrix, igraph, network, cograph_network, or tna object
from	Character or numeric node identifier for the source node.
to	Character or numeric node identifier for the target node.
k	Integer; number of shortest paths to find. Default 3.
weights	Edge weight handling: NULL (default) auto-detects from edge attributes, NA forces unweighted distances, or a numeric vector of custom weights.
directed	Logical or NULL. If NULL (default), auto-detect from matrix symmetry. Set TRUE to force directed, FALSE to force undirected.
...	Additional arguments passed to to_igraph

Details

Yen's algorithm finds the k shortest loopless (simple) paths in a graph. It works by:

1. Finding the shortest path via Dijkstra's algorithm

2. For each subsequent path, systematically exploring deviations from previously found paths by temporarily removing edges, finding spur paths, and selecting the shortest candidate

The algorithm may return fewer than k paths if fewer distinct loopless paths exist between the two nodes.

Value

A list with class "cograph_k_paths" containing:

paths

List of up to k character vectors, each containing node names in path order

distances

Numeric vector of path lengths (sum of edge weights or hop count)

from

Source node name

to

Target node name

k

Number of paths requested

References

Yen, J.Y. (1971). Finding the K shortest loopless paths in a network. Management Science, 17(11), 712-716. \Sexpr[results=rd]{tools:::Rd_expr_doi("10.1287/mnsc.17.11.712")}

See Also

shortest_paths

Examples

# Find 3 shortest paths in a small network
adj <- matrix(c(
  0, 1, 1, 0, 0,
  0, 0, 1, 1, 0,
  0, 0, 0, 1, 1,
  0, 0, 0, 0, 1,
  0, 0, 0, 0, 0
), 5, 5, byrow = TRUE)
rownames(adj) <- colnames(adj) <- LETTERS[1:5]
kp <- cograph::k_shortest_paths(adj, from = "A", to = "E", k = 3)
kp

cograph documentation built on May 31, 2026, 5:06 p.m.