JS implementation Dijkstra's Algorithm

README.md

Basic Implementation of Dijkstra's Algorithm to traverse small node graphs

Code implementation of the following guide for implementing the algorithm

https://isaaccomputerscience.org/concepts/dsa_search_dijkstra

graph.png

graph.spec.ts

import { Graph } from "./graph";

describe("Graph", () => {
  let graph: Graph;

  beforeAll(() => {
    graph = new Graph();
    graph.addNode("A");
    graph.addNode("B");
    graph.addNode("C");
    graph.addNode("D");
    graph.addNode("E");
    graph.addNode("F");

    graph.addEdge(["A", "B"], 3);
    graph.addEdge(["A", "C"], 5);
    graph.addEdge(["B", "D"], 3);
    graph.addEdge(["B", "C"], 3);
    graph.addEdge(["C", "D"], 3);
    graph.addEdge(["C", "E"], 6);
    graph.addEdge(["E", "F"], 1);
    graph.addEdge(["D", "F"], 10);
  });

  it("should return most efficient path from A -> B", () => {
    expect(graph.findShortest("A", "B")).toEqual(["A", "B"]);
  });

  it("should return most efficient path from A -> D", () => {
    expect(graph.findShortest("A", "D")).toEqual(["A", "B", "D"]);
  });

  it("should return most efficient path from A -> F", () => {
    expect(graph.findShortest("A", "F")).toEqual(["A", "C", "E", "F"]);
  });
});

graph.ts

import { find, minBy, pull, reverse } from "lodash";
import { Node, Edge } from "./types";

export class Graph {
  private nodes: Node[] = [];

  private edges: Edge[] = [];

  addNode(id: string) {
    this.nodes.push({ id });
  }

  addEdge(nodes: string[], cost: number) {
    this.edges.push({ nodes, cost });
  }

  /**
   * Calculates the shortest path based on cost from source to destination
   * @param source
   * @param destination
   */
  findShortest(source: string, destination: string) {
    const visited = [];

    const unvisited = this.nodes.map(({ id }) => ({
      node: id,
      cost: Infinity,
      previous: undefined,
    }));
    find(unvisited, { node: source }).cost = 0;

    while (unvisited.length > 0) {
      const currentNode = minBy(unvisited, "cost");

      const costAdjustedNeighbours = this.getNeighbours(currentNode.node)?.map(
        ({ node, cost }) => ({
          node,
          cost: cost + currentNode.cost,
          previous: currentNode.node,
        }),
      );

      costAdjustedNeighbours.forEach(({ node, cost }) => {
        const neighbour = find(unvisited, { node });
        if (neighbour && cost < neighbour.cost) {
          neighbour.cost = cost;
          neighbour.previous = currentNode.node;
        }
      });

      visited.push(currentNode);
      pull(unvisited, currentNode);
    }

    const map = [];
    let current = find(visited, { node: destination });
    while (!map.includes(source)) {
      map.push(current.node);
      current = find(visited, { node: current.previous });
    }

    return reverse(map);
  }

  private getNeighbours(node: string) {
    return this.edges
      .filter(({ nodes }) => nodes?.includes(node))
      .map(({ nodes, cost }) => ({
        node: nodes.find((it) => it !== node),
        cost,
      }));
  }
}

types.ts

export type Node = { id: string };

export type Edge = {
  nodes: string[];
  cost: number;
};