Skip to content

Dijkstra ​

dijkstra(graph, start, end) retorna [path, distance] ou ausência quando o destino é inalcançável. As arestas devem ter pesos i32 não negativos; a entrada pode ser uma lista de adjacência ponderada ou Graph<N, i32>.

AssinaturaRetornaComplexidade
dijkstra(adj: [usize, i32][][], start: usize, end: usize)[usize[], i32]?O((V + E) log V)
dijkstra(graph: Graph<N, i32>, start: usize, end: usize)[usize[], i32]?O((V + E) log V)
tyrus
import { dijkstra } from "tyrus:algorithm";

const result: [usize[], i32]? = dijkstra([[[1, 4], [2, 2]], [[3, 5]], [[3, 1]], []], 0, 3);
if (result) { print(result[0], result[1]); } // [0, 2, 3] 3

Resultado de estudo ​

dijkstraInfo retorna as distâncias provisórias, predecessores, relaxações aceitas, extrações da fila de prioridade e métricas de vértices finalizados para as mesmas formas de entrada.

tyrus
interface DijkstraInfo {
    distances: i32[];
    predecessors: usize?[];
    relaxationCount: usize;
    processedVertexCount: usize;
    examinedEdgeCount: usize;
    heapExtractionCount: usize;
    acceptedRelaxationCount: usize;
    finalizedVertexCount: usize;
}
tyrus
import { DijkstraInfo, ShortestPathInfo, dijkstraInfo } from "tyrus:algorithm";

const info: DijkstraInfo = dijkstraInfo([[[1, 4], [2, 1]], [[3, 1]], [[1, 2], [3, 5]], []], 0, 3);
print(info.distances); // [0, 3, 1, 4]
print(info.predecessors[3] ?? 99); // 1
print(info.relaxationCount); // 5
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 5
print(info.heapExtractionCount); // 5
print(info.acceptedRelaxationCount); // 5
print(info.finalizedVertexCount); // 4