Dijkstra's Algorithm

[RicoLiu]

Using Dijkstra to determine the shortest path

现有如下的一个图，节点是城市，边是城市之间的距离，需要找到从一个城市到另一个城市的最短路径。

起点：San Francisco (SF)，终点：Phoenix (PX). 途中可能经过的城市：Monterey (MT), San Jose (SJ), Santa Barbara (SB), Los Angeles (LA), San Diego (SD), Fresno (FR), Bakersfield (BK), Las Vegas (LV).

首先要初始化所有的变量，一个用来记录经过每一个节点的花费，一个用来记录走过的路径，另一个记录已经访问过的节点以避免重复计算。

这里的 solve() 方法初始化了 costs 变量，并将开始节点的 cost 值赋值给它，然后将结束节点的 cost 值设置为 Infinity. 这就意味着在开始阶段，costs 集合包含了所有的节点和边同样的数据。

var _ = require('lodash');

class Dijkstra {
  solve(graph, start, end) {

    // track costs of each node
    const costs = graph[start];

    // set end to infinite on 1st pass
    costs[end] = Infinity;

    // remember path from
    // which each node was visited
    const paths = {};

    // add path for the start nodes neighbors
    _.forEach(graph[start], (dist, city) => {
      // e.g. city SJ was visited from city SF
      paths[city] = start;
    });

    // track nodes that have already been visited nodes
    const visitedNodes = [];

    // get current nodes cheapest neighbor
    let currentCheapestNode = this.getNextLowestCostUnvisitedNode(costs, visitedNodes);

    // while node exists
    while (currentCheapestNode) {

      // get cost of reaching current cheapest node
      let costToReachCurrentNode = costs[currentCheapestNode];

      // access neighbors of current cheapest node
      let neighbors = graph[currentCheapestNode];

      // loop over neighbors
      _.forEach(neighbors, (dist, neighbor) => {

        // generate new cost to reach each neighbor
        let newCost = costToReachCurrentNode + dist;

        // if not already added
        // or if it is lowest cost amongst the neighbors
        if (!costs[neighbor] || costs[neighbor] > newCost) {

          // add cost to list of costs
          costs[neighbor] = newCost;

          // add to paths
          paths[neighbor] = currentCheapestNode;

        }

      });

      // mark as visited
      visitedNodes.push(currentCheapestNode);

      // get cheapest node for next node
      currentCheapestNode = this.getNextLowestCostUnvisitedNode(costs, visitedNodes);
    }

    // generate response
    let finalPath = [];

    // recursively go to the start
    let previousNode = paths[end];

    while (previousNode) {
      finalPath.unshift(previousNode);
      previousNode = paths[previousNode];
    }

    // add end node at the end
    finalPath.push(end);

    // return response
    return {
      distance: costs[end],
      path: finalPath
    };
  }

  getNextLowestCostUnvisitedNode(costs, visitedNodes) {
    //extract the costs of all non visited nodes
    costs = _.omit(costs, visitedNodes);

    // return the node with minimum cost
    return _.minBy(_.keys(costs), (node) => {
      return costs[node];
    });
  }
}

从上面的代码中可以看出，currentCheapestNode 在首次迭代的时候值为 SJ，基于 costs 和 visitedNodes 数组。

一旦找到了第一个节点，那么就可以访问到它的邻居节点，并且更新 costs 的值（只有在它的 costs 小于当前节点的 cost）.如果 cost 更小，这就说明了我们想通过这个节点到达结束节点是合乎逻辑的，所以也同样更新到他邻居的路径。然后就开始递归的进行这个过程，在递归结束时，我们就能得到更新过后的所有节点的 costs，并且得到到结束节点的最后 cost.

const graph = {
   'SF': { 'SB': 326, 'MT': 118, 'SJ': 49 },
   'SJ': { 'MT': 72, 'FR': 151, 'BK': 241 },
   'MT': { 'SB': 235, 'LA': 320 },
   'SB': { 'LA': 95 },
   'LA': { 'SD': 120 },
   'SD': { 'PX': 355 },
   'FR': { 'LV': 391 },
   'BK': { 'LA': 112, 'SD': 232, 'PX': 483, 'LV': 286 },
   'LV': { 'PX': 297 },
   'PX': {}
};

console.log(new Dijkstra().solve(graph, 'SF', 'PX'));
// { distance: 773, path: [ 'SF', 'SJ', 'BK', 'PX' ] } 

Reference: 《Hands-on Data Structures and Algorithm with JavaScript》