2
\$\begingroup\$

I am writing the solution of Dijkstra's algorithm in JS. This is what has happened so far. I need to make it so that the choice of nodes is by recursion. Tell me how to do this better.

const size = 6;
сonst maxInt = 999999;
const graph = [
  [null, maxInt, 50, 20, maxInt, 30],
  [null, maxInt, maxInt, maxInt, 10, maxInt],
  [null, maxInt, 20, maxInt, 40, maxInt],
  [null, maxInt, maxInt, maxInt, maxInt, maxInt],
  [null, maxInt, 20, maxInt, 25, maxInt]
];

const nodeParams = (distance, path, visited) => {
  this.dist = distance;
  this.path = path;
  this.visited = visited;
};

let node = [];

for(let i = 1;i < size;i++) {
  node[i] = [];
  for(let j = 1;j < size;j++) {
    node[i][j] = nodeParams(maxInt, 0, false);
  }
};

const dijkstra = () => {
  for(let source = 1; source < size; source++) { 
    node[source][source].dist = 0;
    let minNode, nextNode;
    for(let i = 1; i < size - 1; i++) {
      minNode = i === 1 ? source : nextNode;
      node[source][minNode].visited = true;
      nextNode = null;
      for(let w = 1; w < size; w++) {
        if (!node[source][w].visited) {
          if (node[source][minNode].dist + graph[minNode][w] < node[source][w].dist) {
            node[source][w].dist = node[source][minNode].dist + graph[minNode][w];
            node[source][w].path = minNode;
          }
          if(nextNode === null) {
            nextNode = w;
          } 
        }
      }
    }
  }
};

dijkstra ();

let shortestPathString = '';

const getEachPathNode = (source, destination) => {
  if(destination != source && destination > 0) {
    getEachPathNode(source, array[source][destination].path);
    shortestPathString += ' ' + array[source][destination].path;
  }
}

const getShortestPath = (source, destination) => {
  shortestPathString = 'Самый короткий путь от ' + source + ' до ' + destination + ': ';
  if (array[source][destination].dist == maxInt) {
    shortestPathString += 'не связаны';
  } else {
    getEachPathNode(source, destination);
    shortestPathString += ' ' + destination;
  }

  shortestPathString += '.  Расстояние: ' + array[source][destination].dist;
  console.log(shortestPathString);
}

for(let i = 1; i < size; i++) {
  for(let j = 1; j < size; j++) {
    getShortestPath(i, j);
  }
}

If there are any comments on the code, I'll be very glad to hear them too. This code does not go into any project, I just just study programming and try to set myself tasks and solve them.

\$\endgroup\$
  • \$\begingroup\$ Something is wrong with this code. Are you sure it's working? The function nodeParams modifies this which is actually window here, and then returns undefined. You use the return value to create a matrix node, which means you're creating a bunch of undefineds in the matrix. \$\endgroup\$ – Lazar Ljubenović Sep 1 '18 at 9:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.