js实现最短路径算法

Dijkstra算法实现

Dijkstra算法适用于加权图中寻找单源最短路径，要求权重为非负数。以下是JavaScript实现示例：

class PriorityQueue {
  constructor() {
    this.items = [];
  }
  enqueue(element, priority) {
    const queueElement = { element, priority };
    let added = false;
    for (let i = 0; i < this.items.length; i++) {
      if (queueElement.priority < this.items[i].priority) {
        this.items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    if (!added) this.items.push(queueElement);
  }
  dequeue() {
    return this.items.shift();
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

function dijkstra(graph, startNode) {
  const distances = {};
  const previous = {};
  const pq = new PriorityQueue();

  Object.keys(graph).forEach(node => {
    distances[node] = node === startNode ? 0 : Infinity;
    previous[node] = null;
    pq.enqueue(node, distances[node]);
  });

  while (!pq.isEmpty()) {
    const { element: currentNode } = pq.dequeue();
    Object.entries(graph[currentNode]).forEach(([neighbor, weight]) => {
      const alt = distances[currentNode] + weight;
      if (alt < distances[neighbor]) {
        distances[neighbor] = alt;
        previous[neighbor] = currentNode;
        pq.enqueue(neighbor, alt);
      }
    });
  }
  return { distances, previous };
}

Floyd-Warshall算法实现

Floyd-Warshall算法可以计算图中所有顶点对之间的最短路径：

function floydWarshall(graph) {
  const dist = {};
  const vertices = Object.keys(graph);

  vertices.forEach(i => {
    dist[i] = {};
    vertices.forEach(j => {
      dist[i][j] = graph[i][j] || (i === j ? 0 : Infinity);
    });
  });

  vertices.forEach(k => {
    vertices.forEach(i => {
      vertices.forEach(j => {
        if (dist[i][j] > dist[i][k] + dist[k][j]) {
          dist[i][j] = dist[i][k] + dist[k][j];
        }
      });
    });
  });

  return dist;
}

A*搜索算法实现

A*算法结合了Dijkstra和启发式搜索，适用于路径规划：

function aStar(start, goal, graph, heuristic) {
  const openSet = new Set([start]);
  const cameFrom = {};
  const gScore = { [start]: 0 };
  const fScore = { [start]: heuristic(start, goal) };

  while (openSet.size > 0) {
    let current = null;
    let lowestFScore = Infinity;
    openSet.forEach(node => {
      if (fScore[node] < lowestFScore) {
        lowestFScore = fScore[node];
        current = node;
      }
    });

    if (current === goal) {
      return reconstructPath(cameFrom, current);
    }

    openSet.delete(current);
    graph[current].forEach(neighbor => {
      const tentativeGScore = gScore[current] + neighbor.cost;
      if (tentativeGScore < (gScore[neighbor.node] || Infinity)) {
        cameFrom[neighbor.node] = current;
        gScore[neighbor.node] = tentativeGScore;
        fScore[neighbor.node] = gScore[neighbor.node] + heuristic(neighbor.node, goal);
        if (!openSet.has(neighbor.node)) {
          openSet.add(neighbor.node);
        }
      }
    });
  }
  return null;
}

function reconstructPath(cameFrom, current) {
  const path = [current];
  while (cameFrom[current]) {
    current = cameFrom[current];
    path.unshift(current);
  }
  return path;
}

Bellman-Ford算法实现

该算法能处理负权边并检测负权环：

function bellmanFord(graph, start) {
  const distances = {};
  const predecessors = {};
  Object.keys(graph).forEach(node => {
    distances[node] = node === start ? 0 : Infinity;
    predecessors[node] = null;
  });

  for (let i = 0; i < Object.keys(graph).length - 1; i++) {
    Object.entries(graph).forEach(([u, edges]) => {
      Object.entries(edges).forEach(([v, weight]) => {
        if (distances[u] + weight < distances[v]) {
          distances[v] = distances[u] + weight;
          predecessors[v] = u;
        }
      });
    });
  }

  let hasNegativeCycle = false;
  Object.entries(graph).forEach(([u, edges]) => {
    Object.entries(edges).forEach(([v, weight]) => {
      if (distances[u] + weight < distances[v]) {
        hasNegativeCycle = true;
      }
    });
  });

  return { distances, predecessors, hasNegativeCycle };
}

使用注意事项

• Dijkstra算法适用于非负权图，时间复杂度为O((V+E)logV)
• Floyd-Warshall适用于稠密图，时间复杂度O(V³)
• A*算法需要合适的启发式函数
• Bellman-Ford能检测负权环但时间复杂度较高(O(VE))

根据具体场景选择合适算法，例如导航系统常用A*，网络路由常用Dijkstra，需要考虑负权值时使用Bellman-Ford。