javascript 中的 Dijkstra 算法代码片段

Question

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;}

这里，graph是一个结构为(u_vertex,v_vertex,weight)的邻接表，mn 表示当前访问的顶点，graph[mn].length 给出图中所有相邻顶点的总数，dist[ ] 是图中每个顶点与源的存储最小距离 node/vertex，vis 是访问数组，它跟踪通过放置访问的所有顶点1，否则 0

我怀疑的不是算法，而是js代码。所以，在这行代码的时候，让边=图[mn][j];
edge 实际表示什么，变量或数组，其中 edge[0] = j 和 edge[1] = 权重mn & j 个顶点

所以这让我很困惑，因为我从来没有像使用 C++ 那样使用 JS，所以在 C++ 语法意义上 edge 将表示变量，它表示 [= 之间的边的权重30=]mn & j 个顶点，但在 JS 中，这不是真的。所以我需要帮助...

这是邻接表的代码，创建了图...

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);

代码片段

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 1

这与 JS 与 C++ 无关，这只是实现的工作方式。

它不明显的主要原因是代码编写时严重缺乏空格或有意义的变量。这实际上是一个很好的例子，说明了为什么编码风格如此重要。

列表首先初始化为数组列表：

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

然后将graph中的项目添加到这两行：

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

整理了一些有意义的名称和中间变量，即：

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] );
}

所以：

adj_list 是一个包含 number_of_vertices 项的数组
adj_list 中的每一项都是一个边数组
每条边都是一个包含两项的数组
每条边的第一项是顶点号（start或end）
每条边的第二项是权重

在后面的循环中：

mn是顶点数，所以adj_list[mn]是边数组
j是那个数组中的边号，所以adj_list[mn][j]是一条边
这条边被分配给了一个名为 edge
这条边是一个包含两项的数组

同样，我们可以整理变量名，首先将 mn 重命名为 current_vertex，并引入一些额外的变量以使循环可读：

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;
   }
}

我们可以对所有其他代码进行类似的清理，并为 vis 和 dist 提供更好的名称。如果我们想更多地利用该语言，我们还可以使用对象而不是 2 元素数组作为边缘，这样 edge[1] 就可以写成 edge.weight.

javascript 中的 Dijkstra 算法代码片段

Dijkstra Alogrithm code snippet in javascript

javascript

dijkstra