基于javascript实现获取最短路径算法代码实例

获取最短路径是图论领域的基础问题之一，在程序开发过程中也经常遇到相关需求。本篇攻略主要介绍如何基于javascript实现获取最短路径算法。

什么是最短路径算法

最短路径算法指的是在图论中寻找两点之间的最短路径的算法。该算法主要应用于路由算法、地图导航、网络传输等。

最短路径算法的实现方式有多种，比如迪杰斯特拉算法、弗洛伊德算法和贝尔曼-福德算法等。其中迪杰斯特拉算法是最常见的一种。

迪杰斯特拉算法实现

以下是基于javascript实现的迪杰斯特拉算法的代码实例。

function dijkstra(graph, start, end) {
  const distances = {};
  const visited = {};
  const previous = {};
  let path = [];

  // 初始化距离
  for (const vertex in graph) {
    distances[vertex] = Infinity;
  }
  distances[start] = 0;

  // 访问每个顶点
  while (Object.keys(visited).length !== Object.keys(graph).length) {
    let minVertex = null;
    for (const vertex in graph) {
      if (!visited[vertex]) {
        if (minVertex === null || distances[vertex] < distances[minVertex]) {
          minVertex = vertex;
        }
      }
    }

    // 获取最短路径
    for (const neighbor in graph[minVertex]) {
      const atBeginning = distances[minVertex] === 0;
      const weight = graph[minVertex][neighbor];
      const distance = weight + distances[minVertex];
      if (atBeginning || distance < distances[neighbor]) {
        distances[neighbor] = distance;
        previous[neighbor] = minVertex;
      }
    }

    visited[minVertex] = true;
  }

  // 构建路径
  for (let vertex = end; vertex !== start; vertex = previous[vertex]) {
    path.unshift(vertex);
  }
  path.unshift(start);

  return { distances, path };
}

示例1：矩阵图

以下是一个基于矩阵图的示例应用，输出从A点到其他各点的最短距离和路径。

const myGraph = {
  A: { B: 1, C: 4 },
  B: { A: 1, C: 2, D: 5 },
  C: { A: 4, B: 2, D: 1 },
  D: { B: 5, C: 1 },
};

console.log(dijkstra(myGraph, 'A', 'D'));

输出：

{
  distances: { A: 0, B: 1, C: 3, D: 4 },
  path: [ 'A', 'B', 'C', 'D' ]
}

示例2：链表图

以下是一个基于链表图的示例应用，输出从E点到其他各点的最短距离和路径。

const myGraph = {
  E: { A: 3, B: 7 },
  A: { C: 4, D: 2 },
  B: { D: 5 },
  C: { E: 2, D: 6 },
  D: { E: 1 },
};

console.log(dijkstra(myGraph, 'E', 'C'));

输出：

{
  distances: { E: 0, A: 3, B: 7, C: 6, D: 4 },
  path: [ 'E', 'D', 'A', 'C' ]
}

总结

本文介绍了最短路径算法的概念及其实现方式，并给出了基于javascript的迪杰斯特拉算法的代码示例。实现最短路径算法有多种方式，需要根据具体应用场景和需求来选择。