src/app/script.js
/**
   * Dijkstra's algorithm implementation for shortest path.
   * @param {String} source vertex to start from.
   * @param {String} target vertex to find.
   */
Dijkstra's algorithm implementation for shortest path.
@param {String} source vertex to start from.
@param {String} target vertex to find.
Dijkstra ' s algorithm implementation for shortest path . @param { String } source vertex to start from . @param { String } target vertex to find .
dijkstra(source, target) {
    const Q = new Set();
    const prev = {};
    const dist = {};
    const adj = {};
    const vertexMinDist = (Q, d) => {
      let minDist = Infinity;
      let u = null;
      for (const v of Q) {
        if (d[v] < minDist) {
          minDist = d[v];
          u = v;
        }
      }
      return u;
    };
    for (let i = 0; i < this.graph.length; i += 1) {
      const v1 = this.graph[i][0];
      const v2 = this.graph[i][1];
      const len = this.graph[i][2];
      Q.add(v1);
      Q.add(v2);
      dist[v1] = Infinity;
      dist[v2] = Infinity;
      if (adj[v1] === undefined) adj[v1] = {};
      if (adj[v2] === undefined) adj[v2] = {};
      adj[v1][v2] = len;
      adj[v2][v1] = len;
    }
    dist[source] = 0;
    while (Q.size) {
      const u = vertexMinDist(Q, dist);
      const neighbors = Object.keys(adj[u]).filter(v => Q.has(v));
      Q.delete(u);
      if (u === target) break;
      for (const v of neighbors) {
        const alt = dist[u] + adj[u][v];
        if (alt < dist[v]) {
          dist[v] = alt;
          prev[v] = u;
        }
      }
    }
    let u = target;
    const S = [u];
    let edge;
    let len = 0;
    const keys = Object.keys(this.verticies);
    for (let i = 0; i < keys.length; i += 1) {
      if (dist[keys[i]] !== undefined) {
        drawWeight(this.verticies[keys[i]], dist[keys[i]]);
      } else {
        drawWeight(this.verticies[keys[i]], 'Infinity');
      }
    }
    while (prev[u] !== undefined) {
      const vert1 = this.verticies[parseInt(prev[u], 10)];
      const vert2 = this.verticies[parseInt(u, 10)];
      len += adj[u][prev[u]];
      S.unshift(prev[u]);
      edge = vert1.edges[parseInt(u, 10)];
      edge.line.colour = 0x00FF41;
      drawLine(edge.line, vert1.x, vert1.y, vert2.x, vert2.y, edge.line.colour);
      u = prev[u];
    }
    return [S, len];
  }
dijkstra ( source , target ) { const Q = new Set ( ) ; const prev = { } ; const dist = { } ; const adj = { } ; const vertexMinDist = ( Q , d ) => { let minDist = Infinity ; let u = null ; for ( const v of Q ) { if ( d [ v ] < minDist ) { minDist = d [ v ] ; u = v ; } } return u ; } ; for ( let i = 0 ; i < this . graph . length ; i += 1 ) { const v1 = this . graph [ i ] [ 0 ] ; const v2 = this . graph [ i ] [ 1 ] ; const len = this . graph [ i ] [ 2 ] ; Q . add ( v1 ) ; Q . add ( v2 ) ; dist [ v1 ] = Infinity ; dist [ v2 ] = Infinity ; if ( adj [ v1 ] === undefined ) adj [ v1 ] = { } ; if ( adj [ v2 ] === undefined ) adj [ v2 ] = { } ; adj [ v1 ] [ v2 ] = len ; adj [ v2 ] [ v1 ] = len ; } dist [ source ] = 0 ; while ( Q . size ) { const u = vertexMinDist ( Q , dist ) ; const neighbors = Object . keys ( adj [ u ] ) . filter ( v => Q . has ( v ) ) ; Q . delete ( u ) ; if ( u === target ) break ; for ( const v of neighbors ) { const alt = dist [ u ] + adj [ u ] [ v ] ; if ( alt < dist [ v ] ) { dist [ v ] = alt ; prev [ v ] = u ; } } } let u = target ; const S = [ u ] ; let edge ; let len = 0 ; const keys = Object . keys ( this . verticies ) ; for ( let i = 0 ; i < keys . length ; i += 1 ) { if ( dist [ keys [ i ] ] !== undefined ) { drawWeight ( this . verticies [ keys [ i ] ] , dist [ keys [ i ] ] ) ; } else { drawWeight ( this . verticies [ keys [ i ] ] , 'Infinity' ) ; } } while ( prev [ u ] !== undefined ) { const vert1 = this . verticies [ parseInt ( prev [ u ] , 10 ) ] ; const vert2 = this . verticies [ parseInt ( u , 10 ) ] ; len += adj [ u ] [ prev [ u ] ] ; S . unshift ( prev [ u ] ) ; edge = vert1 . edges [ parseInt ( u , 10 ) ] ; edge . line . colour = 0x00FF41 ; drawLine ( edge . line , vert1 . x , vert1 . y , vert2 . x , vert2 . y , edge . line . colour ) ; u = prev [ u ] ; } return [ S , len ] ; }
Dijkstra's algorithm implementation for shortest path.
Dijkstra ' s algorithm implementation for shortest path .