Function dijkstra

src/13-graph/dijkstra.ts:24–62

(
  graph: number[][],
  src: number
)

 * @complexity Time O(V²) | Space O(V)
 */
const dijkstra = (
  graph: number[][],
  src: number
): { distances: number[]; predecessors: Record<number, number[]> } => {
  const dist: number[] = [];
  const visited: boolean[] = [];
  const pred: (number | null)[] = []; // Predecessor array
  const { length } = graph;
  for (let i = 0; i < length; i++) {
    dist[i] = INF;
    visited[i] = false;
    pred[i] = null; // Initialize predecessors
  }
  dist[src] = 0;
  for (let i = 0; i < length - 1; i++) {
    const unv = minDistance(dist, visited);
    visited[unv] = true;
    for (let v = 0; v < length; v++) {
      if (!visited[v] && graph[unv][v] !== 0 && dist[unv] !== INF && dist[unv] + graph[unv][v] < dist[v]) {
        dist[v] = dist[unv] + graph[unv][v];
        pred[v] = unv; // Update predecessor
      }
    }
  }

  // Construct paths from predecessors
  const paths: Record<number, number[]> = {};
  for (let i = 0; i < length; i++) {
    paths[i] = [];
    let crawl: number = i;
    paths[i].push(crawl);
    while (pred[crawl] !== null) {
      paths[i].push(pred[crawl]!);
      crawl = pred[crawl]!;
    }
    paths[i].reverse();
  }
  return { distances: dist, predecessors: paths };
};

export default dijkstra;