dijkstra算法记录路径

Dijkstra算法是一种单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。在Dijkstra算法中，我们可以通过记录每个节点的前驱节点来记录路径。具体实现如下：

1. 初始化一个distance数组，用来记录源节点到每个节点的距离，对于源节点，距离为0，对于其他节点，距离为无穷大。
2. 初始化一个visited数组，用来记录每个节点的访问状态，对于源节点，访问状态为true，对于其他节点，访问状态为false。
3. 初始化一个predecessor数组，用来记录每个节点的前驱节点，对于源节点，前驱节点为null，对于其他节点，前驱节点为undefined。
4. 将源节点加入一个优先队列中。
5. 从优先队列中取出一个节点，标记其为已访问，遍历其所有邻居节点，如果该邻居节点未被访问，则计算源节点到该邻居节点的距离，如果该距离小于distance数组中该节点的距离，则更新distance数组和predecessor数组，并将该邻居节点加入优先队列中。
6. 重复步骤5，直到所有节点都被访问过。
7. 根据predecessor数组可以得到源节点到每个节点的最短路径。

下面是一个JavaScript实现示例：

function dijkstra(graph, source) {
  var distance = [];
  var visited = [];
  var predecessor = [];
  var queue = new PriorityQueue();

  for (var i = 0; i < graph.length; i++) {
    distance[i] = Infinity;
    visited[i] = false;
    predecessor[i] = undefined;
  }

  distance[source] = 0;
  queue.enqueue(source, 0);

  while (!queue.isEmpty()) {
    var u = queue.dequeue();

    if (visited[u]) {
      continue;
    }

    visited[u] = true;

    for (var v = 0; v < graph[u].length; v++) {
      if (graph[u][v] !== 0 && !visited[v]) {
        var alt = distance[u] + graph[u][v];

        if (alt < distance[v]) {
          distance[v] = alt;
          predecessor[v] = u;
          queue.enqueue(v, distance[v]);
        }
      }
    }
  }

  return predecessor;
}

注：上述实现中，我们使用了一个优先队列来存储节点和节点距离，这样可以保证每次取出的是距离最小的节点，从而保证算法的正确性。你可以使用任何优先队列实现，例如JavaScript中的数组，Java中的PriorityQueue等。