Johnson
johnson(graph) calcula menores caminhos entre todos os pares em grafos ponderados esparsos combinando reponderação com Dijkstra. Um ciclo negativo retorna Err(AlgorithmError) com o código ERR_ALGORITHM_NEGATIVE_CYCLE; propague-o com ? ou trate-o com match.
| Assinatura | Retorna | Complexidade |
|---|---|---|
johnson(adj: [usize, i32][][]) | Result<(i32?)[][], AlgorithmError> | O(VE + V(V + E) log V) |
tyrus
import { AlgorithmError, johnson } from "tyrus:algorithm";
const showDistances = (): Result<void, AlgorithmError> => {
const distances = johnson([[[1, 4], [2, 2]], [[3, 5]], [[3, 1]], []])?;
print(distances[0][3] ?? -1); // 3
return Ok();
};
match (showDistances()) {
Ok(_) => {}
Err(error) => { printError(error.code); // ERR_ALGORITHM_NEGATIVE_CYCLE
}
}Resultado de estudo
johnsonInfo retorna Result<JohnsonInfo, AlgorithmError> com a matriz de distâncias de todos os pares, a contagem de reponderações, as relaxações do Bellman-Ford inicial e as execuções de Dijkstra.
tyrus
interface JohnsonInfo {
distances: i32?[][];
reweightingCount: usize;
bellmanFordRelaxationCount: usize;
dijkstraExecutionCount: usize;
}tyrus
import { AlgorithmError, JohnsonInfo, johnsonInfo } from "tyrus:algorithm";
const showStudy = (): Result<void, AlgorithmError> => {
const info: JohnsonInfo = johnsonInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []])?;
print(info.distances[0][3] ?? -1); // 4
print(info.reweightingCount); // 5
print(info.bellmanFordRelaxationCount); // 4
print(info.dijkstraExecutionCount); // 4
return Ok();
};
match (showStudy()) {
Ok(_) => {}
Err(error) => { printError(error.code); // ERR_ALGORITHM_NEGATIVE_CYCLE
}
}