SPFA
spfa(graph, start) computes single-source shortest paths with negative weights and returns distances plus predecessors. A negative cycle returns Err(AlgorithmError) with code ERR_ALGORITHM_NEGATIVE_CYCLE; propagate it with ? or handle it with match.
| Signature | Returns | Complexity |
|---|---|---|
spfa(adj: [usize, i32][][], start: usize) | Result<[i32[], usize?[]], AlgorithmError> | O(VE) worst case, O(V) memory |
tyrus
import { AlgorithmError, spfa } from "tyrus:algorithm";
const showPaths = (): Result<void, AlgorithmError> => {
const result = spfa([[[1, 2]], [[2, -1]], []], 0)?;
print(result[0][2]); // 1
return Ok();
};
match (showPaths()) {
Ok(_) => {}
Err(error) => { printError(error.code); // ERR_ALGORITHM_NEGATIVE_CYCLE
}
}Study result
spfaInfo returns Result<SpfaInfo, AlgorithmError> and adds queue pushes, queue pops, maximum queue size, and the shared shortest-path metrics. A reachable negative cycle is returned as Err(AlgorithmError).
tyrus
interface SpfaInfo {
distances: i32[];
predecessors: usize?[];
relaxationCount: usize;
processedVertexCount: usize;
examinedEdgeCount: usize;
queuePushCount: usize;
queuePopCount: usize;
maxQueueSize: usize;
}tyrus
import { AlgorithmError, SpfaInfo, spfaInfo } from "tyrus:algorithm";
const showStudy = (): Result<void, AlgorithmError> => {
const info: SpfaInfo = spfaInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], 0)?;
print(info.distances); // [0, 3, 1, 4]
print(info.predecessors[3] ?? 99); // 1
print(info.relaxationCount); // 5
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 6
print(info.queuePushCount); // 6
print(info.queuePopCount); // 6
print(info.maxQueueSize); // 2
return Ok();
};
match (showStudy()) {
Ok(_) => {}
Err(error) => { printError(error.code); // ERR_ALGORITHM_NEGATIVE_CYCLE
}
}