[
  [1, 2],
  [0, 3],
  [0, 4],
  [1],
  [2]
];

function Graph(v) {
  // 顶点数
  this.vertices = v;
  // 边数
  this.edges = 0;
  // 邻接表
  this.adj = [];
  for (var i = 0; i < this.vertices; i++) {
    this.adj[i] = [];
  }
}
Graph.prototype = {
  addEdge(v, w) {
    this.adj[v].push(w);
    this.adj[w].push(v);
    this.edges++;
  },
  // 深度优先搜索
  dfs(v) {
    if (this.adj[v] === undefined) {
      return;
    }
    var stack = [v];
    var visited = new Set();
    visited.add(v);
    while (stack.length) {
      var vertex = stack.pop();
      var nodes = this.adj[vertex];
      for (var w of nodes) {
        if (!visited.has(w)) {
          stack.push(w);
          visited.add(w);
        }
      }
      console.log("dfs:", vertex);
    }
  },
  // 广度优先搜索
  bfs(v) {
    if (this.adj[v] === undefined) {
      return;
    }
    var que = [v];
    var visited = new Set();
    visited.add(v);
    var parent = [];
    parent[v] = null;
    while (que.length) {
      var vertex = que.shift();
      var nodes = this.adj[vertex];
      for (var w of nodes) {
        if (!visited.has(w)) {
          que.push(w);
          visited.add(w);
          parent[w] = vertex;
        }
      }
      console.log("bfs:", vertex);
    }
    return parent;
  },
  // 求两顶点间最短路径
  minPath(start, end) {
    var parent = this.bfs(start);
    var path = [];
    while (end !== null) {
      path.push(end);
      end = parent[end];
    }
    return path.reverse().join(" -> ");
  },
};
var g = new Graph(5);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.dfs(0);
g.minPath(0, 4);

var graph = {
  A: { B: 5, C: 1 },
  B: { A: 5, C: 2, D: 1 },
  C: { A: 1, B: 2, D: 4, E: 8 },
  D: { B: 1, C: 4, E: 3, F: 6 },
  E: { C: 8, D: 3 },
  F: { D: 6 },
};

function El(data, code) {
  this.data = data;
  this.code = code;
}
function PriorityQue() {
  this.dataStore = [];
  this.head = 0;
  this.tail = 0;
  this.length = 0;
}
PriorityQue.prototype = {
  enque(data, code) {
    var el = new El(data, code);
    this.dataStore[this.tail++] = el;
    this.dataStore.sort((a, b) => a.code - b.code);
    this.length++;
  },
  deque() {
    if (this.head === this.tail) {
      return null;
    }
    this.length--;
    return this.dataStore[this.head++];
  },
};

function initDistance(s) {
  var distance = {};
  for (var vertex in graph) {
    distance[vertex] = Infinity;
  }
  distance[s] = 0;
  return distance;
}
function dijkstra(s) {
  var pque = new PriorityQue();
  pque.enque(s, 0);
  var visited = [];
  var parent = {};
  parent[s] = null;
  var distance = initDistance(s);
  while (pque.length) {
    // 当队列处理完成时，就找到了最优的路径
    var pair = pque.deque();
    var vertex = pair.data;
    var dist = pair.code;

    var nodes = Object.keys(graph[vertex]);
    for (var item of nodes) {
      if (!visited.includes(item)) {
        // 关键 不断更新弹出的顶点到起始点的最短距离
        if (dist + graph[vertex][item] < distance[item]) {
          pque.enque(item, dist + graph[vertex][item]);
          parent[item] = vertex;
          distance[item] = dist + graph[vertex][item];
        }
      }
    }
  }
  return { parent, distance };
}
function pathTo(s, e) {
  var { parent, distance } = dijkstra(s);
  var path = [e];
  var tmp = parent[e];
  while (tmp) {
    path.push(tmp);
    tmp = parent[tmp];
  }
  return path.reverse().join(" -> ") + ` 最短距离: ${distance[e]}`;
}
pathTo("A", "F");