18 Weighted & Directional Graph and Dijkstra's Algorithm in JavaScript

graph.js

// Weighted directional graph implementation and Dijkstra's algorithm

class Graph {

  constructor() {
    this.vertices = [];
    this.edges = [];
  }

  // add a sequence of vertices to the graph
  add(...items){
    for (var i = 0; i < items.length; i++) {
      var item = items[i];
      if(this.getVertex(item)) return;
      this.vertices.push(new Vertex(items[i]));
    }
  }

  // connect source vertex to destination vertex using an edge with weight
  connect(src, dest, weight) {
    if(!this.connected(src, dest)){
      var v1 = this.getVertex(src);
      var v2 = this.getVertex(dest);
      this.edges.push(new Edge(v1, v2, weight));
    }
  }

  // private method to examine if two vertex have already been connected
  connected(src, dest) {
    return this.getVertex(src) && this.getVertex(dest) && this.getEdge(src, dest);
  }

  // private method to get a vertex according to data
  getVertex(data){
    return this.vertices.filter((v) => {
      return v.data == data;
    })[0];
  }

  // private method to get an edge according to source and destination data
  getEdge(src, dest){
    return this.edges.filter((e) => {
      return e.src.data == src && e.dest.data == dest;
    })[0];
  }

  // private method to get connected vertices to the given vertex
  getAdjacents(v){
    var adjacents = [];
    for (var i = 0; i < this.edges.length; i++) {
      var edge = this.edges[i];
      if(edge.hasVertex(v)){
        adjacents.push(edge.dest);
      }
    }
    return adjacents;
  }

  // private method to clear all visited flag for vertices
  clearVisited(){
    for (var i = 0; i < this.vertices.length; i++) {
      this.vertices[i].visited = false;
    }
  }

  traverseFrom(src){
    this.clearVisited();
    var start = this.getVertex(src);
    this.tr(start);
  }

  // function to be recursively called in traversing graph
  tr(v){
    var stack = [];
    stack.push(v);
    console.log(v.data + " is visited");
    v.visited = true;
    while(stack.length > 0){
      var first = stack.shift();
      var adjacents = this.getAdjacents(first);
      for (var i = 0; i < adjacents.length; i++) {
        var adjacent = adjacents[i];
        if(adjacent.visited == false){
          adjacent.visited = true;
          // Depth first search
          // stack.unshift(adjacent);
          // Breath first search
          stack.push(adjacent);
          console.log(adjacent.data + " is visited");
        }
      }
    }
  }

  getShortestPath(src, dest){
    src = this.getVertex(src);
    dest = this.getVertex(dest);

    this.dijkstraInit(src);

    // this function is recursively called, to get costs for all vertices
    // but will break when the cost of destination vertex is calculated
    this.dijkstra(dest);
    var v = dest;
    var path = dest.data;
    var cost = v.cost;
    while(true){
      v = v.parent;
      if(!v){
        break;
      }else{
        path = v.data + " -> " + path;
      }
    }
    return {
      path, cost
    };
  }

  // function to be recursively called in searching for a shortest path in graph
  dijkstra(dest){
    // find next unvisited vertex with lowest cost
    var next = this.getVertexWithLowestCost();
    if(!next || next == dest) return;
    // get its unvisited adjacent vertices
    var adjacents = this.getAdjacents(next);
    // update costs for all adjacents
    adjacents.forEach((v) => {
      var newCost = next.cost + this.getEdge(next.data, v.data).weight;
      if(newCost < v.cost){
        v.cost = newCost;
        v.parent = next;
      }
    });
    next.visited = true;
    this.dijkstra(dest);
  }

  // private method to initialize graph before the dijkstra's algorithm: clear visited and set initial costs 
  dijkstraInit(src){
    for (var i = 0; i < this.vertices.length; i++) {
      var v = this.vertices[i];
      if(v.data == src.data){
        v.cost = 0;
        v.visited = true;
      }else if(this.connected(src.data, v.data)){
        v.cost = this.getEdge(src.data, v.data).weight;
        v.parent = src;
        v.visited = false;
      }else{
        v.cost = Infinity;
        v.visited = false;
      }
    }
  }

  // private method in dijkstra's algorithm
  getVertexWithLowestCost(){
    var i = 0;
    var j = -1;
    var minCost = Infinity;
    var unvisitedVerticies = this.vertices.filter((v) => {
      return v.visited == false;
    });
    while(i < unvisitedVerticies.length){
      var v = unvisitedVerticies[i];
      if(v.cost < minCost){
        j = i;
        minCost = v.cost;
      }
      i++;
    }
    return unvisitedVerticies[j];
  }
}

class Vertex {
  constructor(data){
    this.data = data;
  }
}

class Edge {
  constructor(src, dest, weight){
    this.src = src;
    this.dest = dest;
    this.weight = weight;
  }

  hasVertex(v){
    return v.data == this.src.data
  }
}

// test
var graph = new Graph();

graph.add("start","a","b","finish");
graph.connect("start","a",6);
graph.connect("start","b",2);
graph.connect("b","a",3);
graph.connect("a","finish",1);
graph.connect("b","finish",5);

graph.traverseFrom("b");
/*
b is visited
a is visited
finish is visited
*/

var result = graph.getShortestPath("start","finish");
console.log(result);
// { path: 'start -> b -> a -> finish', cost: 6 }

var result = graph.getShortestPath("start","a");
console.log(result);
// { path: 'start -> b -> a', cost: 5 }

The code above created a graph depicted  in the following image from Aditya Y. Bhargava's Grokking Algorithms
https://lh3.googleusercontent.com/EFmLaymrBXUtDdKs86hC_lyxGE1sjQoFBJ2J9wBkQA6uPIQZ3MI-6DfKQmPfX_SuSQJwRATuNl-wOHit0qxVpzWm5wyPELeWvOwbQ4ShC8UeHyHsQ49igSguBrCkBAbNjHMV4-IfaBKKGSN0kX1U6sRzjkS3WhcxqQE5AYuF5lOjV_LnDteCZ4N6GGSO9_HPeoeg6ZK8p7oig2XcBOkaOqYuSKyVPdKRXweVc_2AROZv0YysJrKVFJLua1ugf5htwuHn2V86frHgJpDTWIZDM5XqCgqVXcZDOO4hcWol8RduxpmDCFao2S0sgwzn3SF0l1f4hyIO2trLbj4Fneq1_S8oUATQEP2W9hYEju8nnhzqD9xh4geXTe4XvxziflKBGIj8YHxEK0lkhf1K-m6lnCINtI4jq9Lbeq90NdTfKQwDLTS-dNUrz2slPcU6IIEPE8F4EKhMTEPUVxypfznhp9JChfS9Sqj2Uy7O9j7vf6vCnOorvUHBLZQk8_OivY34wqga3UFw49Xb0qNOAvxtdtKXeocU2pCyJBAlyFfoWqjKeLdwvyCZGJDHWE5uea-L8w56vaztzrOu93WyVoMMPsuTDTr63UzSxGi8tpOJOidCjrCr=w466-h289-no