javascript - 在 javascript 中实现 dijkstra 算法时出错

Question

我根据wiki中给出的伪代码制作了这段代码。仍然有一些错误。请帮助我编写代码并告诉我如何改进它我正在尝试几个小时！我已将我知道的那行标记为错误。休息一下，我不知道我哪里错了

  var graph = [{
        from: [1, 2, 3, 4],
        to: [3, 3, 5, 6]
    }];
    var shortestpath = function (graph, source) {
            for (i in graph) {
                dist[i] = infinty;
                prev[i] = undefined;
            }
            dist[source] = 0;
            var q = [];
            q.push(graph.value);
            while (q != 0) {
               var min_distance = infinity;
var u = null;

for (var i in dist) {
   if (dist[i] < min_distance) {
      u = i;
      min_distance = dist[u];
   }
}
                if (dist[u] = infinity) {
                    break;
                }
                q.pop(u);
                for (v in u) {
                    var alt = dist[u] + dist_between(u, v);
                    if (alt < dist[v]) {
                        dist[v] = alt;
                        previous[v] = u;
                        q.sort(v);
                    }
                }
            }
            return dist;
        }
    }

Answer 1

根据Dijkstra 的算法伪代码， u 不应该是一个列表，而是一个简单的 int，它保存着距离 in 小的顶点的索引 Q。

如果您想要距离最小的顶点，则必须遍历 vertices array ，跟踪到目前为止找到的最小距离，并分配给 u具有此距离的顶点。

var min_distance = infinity;
var u = null;

for (var i in dist) {
   if (dist[i] < min_distance) {
      u = i;
      min_distance = dist[u];
   }
}