Dijkstra Alogrithm code snippet in javascript

function djikstra(graph, V, src) {
    let vis = Array(V).fill(0);
    let dist = [];
    for(let i=0;i<V;i++)
    dist.push([10000,-1]);
    dist[src][0] = 0;

    for(let i=0;i<V-1;i++){
       let mn = -1;
       for(let j=0;j<V;j++){
          if(vis[j]===0){
             if(mn===-1 || dist[j][0]<dist[mn][0])
                mn = j;
          }
       }

       vis[mn] = 1;
       for(let j=0;j<graph[mn].length;j++){
          let edge = graph[mn][j];
          if(vis[edge[0]]===0 && dist[edge[0]][0]>dist[mn][0]+edge[1]){
              dist[edge[0]][0] = dist[mn][0]+edge[1];
              dist[edge[0]][1] = mn;
          }
       }
    }
    return dist;}

In here, graph is an adjacency list with a structure (u_vertex,v_vertex,weight), mn signifies the current vertices that’s visited right now and graph[mn].length gives the total number of all the neighboring vertices that’s present in the graph, dist[] is a storing minimum distance for every vertices in the graph from source node/vertex, vis is the visited array which track all the vertices which are visited by putting 1, otherwise 0

My doubt isn’t in the Algorithm, it’s in the js code. So, in this line of code when, let edge = graph[mn][j];
what edge actually signifies, a variable or an array where edge[0] = j and edge[1] = weight of mn & j vertices

So that’s very confusing to me because I never used JS like I do C++, so in C++ syntax sense that edge would represent variable which signifies weight of the edge between mn & j vertices but in JS, it’s not true. So I need help…

And this is the code of Adjacency list, the graph is created…

function createGraph(V,E){
    // V - Number of vertices in graph
    // E - Number of edges in graph (u,v,w)
    let adj_list = []; // Adjacency list
    for(let i = 0 ; i < V ; i++){
        adj_list.push([]);
    }
    for(let i = 0 ; i < E.length ; i++){
        adj_list[E[i][0]].push([E[i][1],E[i][2]]);
        adj_list[E[i][1]].push([E[i][0],E[i][2]]);
    }
    return adj_list;
}
let src = 0;
let V = 9;
let E = [[0,1,4], [0,7,8], [1,7,11], [1,2,8], [7,8,7], [6,7,1], [2,8,2],[6,8,6], [5,6,2], [2,5,4], [2,3,7], [3,5,14], [3,4,9], [4,5,10]];
let graph = createGraph(V,E);
let distances = djikstra(graph,V,0);
console.log(distances);

Snippet of code

function djikstra(graph, V, src) {
  let vis = Array(V).fill(0);
  let dist = [];
  for (let i = 0; i < V; i++)
    dist.push([10000, -1]);
  dist[src][0] = 0;

  for (let i = 0; i < V - 1; i++) {
    let mn = -1;
    for (let j = 0; j < V; j++) {
      if (vis[j] === 0) {
        if (mn === -1 || dist[j][0] < dist[mn][0])
          mn = j;
      }
    }

    vis[mn] = 1;
    for (let j = 0; j < graph[mn].length; j++) {
      let edge = graph[mn][j];
      if (vis[edge[0]] === 0 && dist[edge[0]][0] > dist[mn][0] + edge[1]) {
        dist[edge[0]][0] = dist[mn][0] + edge[1];
        dist[edge[0]][1] = mn;
      }
    }
  }
  return dist;
}

function createGraph(V, E) {
  // V - Number of vertices in graph
  // E - Number of edges in graph (u,v,w)
  let adj_list = []; // Adjacency list
  for (let i = 0; i < V; i++) {
    adj_list.push([]);
  }
  for (let i = 0; i < E.length; i++) {
    adj_list[E[i][0]].push([E[i][1], E[i][2]]);
    adj_list[E[i][1]].push([E[i][0], E[i][2]]);
  }
  return adj_list;
}
let src = 0;
let V = 9;
let E = [
  [0, 1, 4],
  [0, 7, 8],
  [1, 7, 11],
  [1, 2, 8],
  [7, 8, 7],
  [6, 7, 1],
  [2, 8, 2],
  [6, 8, 6],
  [5, 6, 2],
  [2, 5, 4],
  [2, 3, 7],
  [3, 5, 14],
  [3, 4, 9],
  [4, 5, 10]
];
let graph = createGraph(V, E);
let distances = djikstra(graph, V, 0);
console.log(distances);

Answer

This has nothing to do with JS vs C++, it’s just the way the implementation works.

The main reason it’s not obvious is that the code is written with a horrible lack of whitespace or meaningful variables. This is actually a really good example of why coding style is so important.

The list is first initialised as a list of arrays:

let adj_list = [];
for(let i = 0 ; i < V ; i++){
    adj_list.push([]);
}

Then the items in graph are added in these two lines:

adj_list[E[i][0]].push([E[i][1],E[i][2]]);
adj_list[E[i][1]].push([E[i][0],E[i][2]]);

Tidied up with some meaningful names and intermediate variables, that’s:

let adj_list = [];

for(let vertex_number = 0 ; vertex_number < number_of_vertices ; vertex_number++){
   adj_list[ vertex_number ] = [];
}

for(let edge_number = 0 ; edge_number < edge_list.length ; edge_number++) {
   let edge = edge_list[edge_number];
   let start = edge[0], end = edge[1], weight = edge[2];
   
   adj_list[ start ].push( [end, weight] );
   adj_list[ end ].push( [start, weight] );
}

So:

  • adj_list is an array with number_of_vertices items
  • each item in adj_list is an array of edges
  • each edge is an array with two items
  • the first item in each edge is a vertex number (start or end)
  • the second item in each edge is a weight

In the later loop:

  • mn is the vertex number, so adj_list[mn] is an array of edges
  • j is the edge number in that array, so adj_list[mn][j] is an edge
  • the edge is assigned to a variable called edge
  • that edge is an array with two items in it

Again, we can tidy up the variable names, starting by renaming mn as current_vertex, and introducing some extra variables to make the loop readable:

let current_edge_list = graph[current_vertex];
for(let edge_number=0; edge_number < current_edge_list.length; edge_number++) {
   let edge = current_edge_list[edge_number];
   let edge_end=edge[0], edge_weight=edge[1];
   if(
      vis[edge_end] === 0 
      && 
      dist[edge_end][0] > dist[current_vertex][0] + edge_weight
   ) {
      dist[edge_end][0] = dist[current_vertex][0] + edge_weight;
      dist[edge_end][1] = current_vertex;
   }
}

We could do similar cleanup on all the other code, and give vis and dist better names. If we wanted to take more advantage of the language, we could also use objects rather than 2-element arrays for the edges, so that edge[1] could be written edge.weight.