Move History

Fork Selected
  • Algorithms
    Logic
    Description

    Based on the pseudocode at: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

    Please check the test cases for an example input.

    Code
    function dijkstra(numberOfVertices, edges, source, target) {
      if (target >= numberOfVertices) throw new Error('target outside available vertices');
      if (source < 0 || numberOfVertices === 0) throw new Error('source outside available vertices');
    
      const dist = {};
      const prev = {};
      const q = [];
      
      for (let v = 0; v < numberOfVertices; v++) {
        dist[v] = Infinity;
        prev[v] = null;
        q.push(v);
      }
      dist[source] = 0;
      
      while (q.length) {
        // Node with the least distance will be selected first
        const u = q.reduce((minV, v) => dist[v] < dist[minV] ? v : minV );
        
        if (u === target) break;
        
        // Remove u from q
        q.splice(q.indexOf(u), 1);
        
        (edges[u] || [])
          .forEach(edge => {
            const alt = dist[u] + edge.cost;
            if (alt < dist[edge.to]) {
              dist[edge.to] = alt;
              prev[edge.to] = u;
            }
          });
      }
    
      if (dist[target] === Infinity) return null;
      
      const s = [];
      let u = target;
      while (prev[u] !== null) {
        s.unshift(u);
        u = prev[u];
      }
      s.unshift(u);
      return s;
    }
    Test Cases
    const numberOfVertices = 5; // 0, 1, 2, 3, 4
    const edges = {
    0: [{ to: 1, cost: 2}],
    1: [{ to: 0, cost: 1},
      { to: 2, cost: 3},
      { to: 3, cost: 10}],
    3: [{ to: 4, cost: 2}]};
    const start = 0;
    const finish = 4;
    
    describe("Examples", function() {
      it("should return the best path", function() {
        const path = dijkstra(numberOfVertices, edges, start, finish);
        console.log(path);
        Test.assertSimilar(path, [0, 1, 3, 4], "Returns the correct path");
      });
      
      it("should return null when no path is possible", function() {
        const path = dijkstra(numberOfVertices + 1, edges, start, finish + 1);
        console.log(path);
        Test.assertEquals(path, null, "Returns null");
      });
      
      it("should throw an error if target is outside the available vertices", function() {
        Test.expectError(() => dijkstra(numberOfVertices, edges, start, finish + 1));
      });
      
      it("should throw an error if source is outside the available vertices", function() {
        Test.expectError(() => dijkstra(numberOfVertices, edges, start - 1, finish));
        Test.expectError(() => dijkstra(0, edges, 0, 0));
      });
    });