狄克斯特拉算法 理解

[sailei1]

//   构建图形
const graph = {};
graph["start"] = {};
graph["start"]["a"] = 6;
graph["start"]["b"] = 2;

graph["a"] = {};
graph["a"]["fin"] = 1;

graph["b"] = {};
graph["b"]["a"] = 3;
graph["b"]["fin"] = 5;

graph["fin"] = {}; //终点
// 起点花费
const costs = {};
costs['a'] = 6;
costs['b'] = 2;
costs['fin'] = Infinity;
//构建节点关系
const parents = {};
parents['a'] = 'start';
parents['b'] = 'start';
parents['fin'] = null;

let processed = []; // 用于存储查询节点的标记

//找到最低花费节点
function find_lowest_cost_node(costs) {
  debugger;
  let lowest_cost = Infinity;
  let lowest_cost_node = null;

  // Go through each node
  for (let node in costs) {
    let cost = costs[node];
    // If it's the lowest cost so far and hasn't been processed yet...
    if (cost < lowest_cost && (processed.indexOf(node) === -1)) {
      // ... set it as the new lowest-cost node.
      lowest_cost = cost;
      lowest_cost_node = node;
    }
  }
  return lowest_cost_node;
}
//从起点花费开始找
let node = find_lowest_cost_node(costs);

//循环到终点跳转
while (node !== null) {
  let cost = costs[node];
  // Go through all the neighbors of this node
  let neighbors = graph[node];
  Object.keys(neighbors).forEach(function(n) {
    let new_cost = cost + neighbors[n];
    // If it's cheaper to get to this neighbor by going through this node
    if (costs[n] > new_cost) {
      // ... update the cost for this node
      costs[n] = new_cost;
      // This node becomes the new parent for this neighbor.
      parents[n] = node;
    }
  });

  // Mark the node as processed
  processed = processed.concat(node);

  // Find the next node to process, and loop
  node = find_lowest_cost_node(costs);
}

console.log("Cost from the start to each node:");
console.log(costs); // { a: 5, b: 2, fin: 6 }

思路：

1 找出最便宜的节点，即可在最短时间内前往的节点。 2 对于该节点的邻居，检查是否有前往它们都得更短路径，如果有，就更新其花费。 3 重复这个过程，直到对图中的每个节点都这样做 4 计算最终路径