// Dijkstra 算法实现
class Dijkstra {
  constructor(graph) {
    this.graph = graph;
  }
  
  // 找到最短路径
  findShortestPath(start, end) {
    const distances = new Map();
    const previous = new Map();
    const unvisited = new Set();
    
    // 初始化
    const vertices = this.graph.getVertices();
    for (const vertex of vertices) {
      distances.set(vertex, Infinity);
      unvisited.add(vertex);
    }
    distances.set(start, 0);
    
    while (unvisited.size > 0) {
      // 找到距离最小的未访问顶点
      let current = null;
      let minDistance = Infinity;
      
      for (const vertex of unvisited) {
        const distance = distances.get(vertex);
        if (distance < minDistance) {
          minDistance = distance;
          current = vertex;
        }
      }
      
      if (current === null) break;
      
      unvisited.delete(current);
      
      // 如果到达目标顶点，可以提前结束
      if (current === end) break;
      
      // 更新邻居距离
      const neighbors = this.graph.getNeighbors(current);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const weight = neighbor.weight || 1;
        
        if (unvisited.has(neighborVertex)) {
          const newDistance = distances.get(current) + weight;
          if (newDistance < distances.get(neighborVertex)) {
            distances.set(neighborVertex, newDistance);
            previous.set(neighborVertex, current);
          }
        }
      }
    }
    
    // 重建路径
    return this.reconstructPath(previous, start, end, distances);
  }
  
  // 重建路径
  reconstructPath(previous, start, end, distances) {
    if (distances.get(end) === Infinity) {
      return null; // 不可达
    }
    
    const path = [];
    let current = end;
    
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current);
    }
    
    return {
      path: path,
      distance: distances.get(end)
    };
  }
  
  // 找到到所有顶点的最短路径
  findAllShortestPaths(start) {
    const distances = new Map();
    const previous = new Map();
    const unvisited = new Set();
    
    // 初始化
    const vertices = this.graph.getVertices();
    for (const vertex of vertices) {
      distances.set(vertex, Infinity);
      unvisited.add(vertex);
    }
    distances.set(start, 0);
    
    while (unvisited.size > 0) {
      // 找到距离最小的未访问顶点
      let current = null;
      let minDistance = Infinity;
      
      for (const vertex of unvisited) {
        const distance = distances.get(vertex);
        if (distance < minDistance) {
          minDistance = distance;
          current = vertex;
        }
      }
      
      if (current === null) break;
      
      unvisited.delete(current);
      
      // 更新邻居距离
      const neighbors = this.graph.getNeighbors(current);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const weight = neighbor.weight || 1;
        
        if (unvisited.has(neighborVertex)) {
          const newDistance = distances.get(current) + weight;
          if (newDistance < distances.get(neighborVertex)) {
            distances.set(neighborVertex, newDistance);
            previous.set(neighborVertex, current);
          }
        }
      }
    }
    
    return { distances, previous };
  }
}

// 使用优先队列优化的 Dijkstra 算法
class PriorityQueue {
  constructor() {
    this.queue = [];
  }
  
  enqueue(element, priority) {
    this.queue.push({ element, priority });
    this.queue.sort((a, b) => a.priority - b.priority);
  }
  
  dequeue() {
    return this.queue.shift()?.element;
  }
  
  isEmpty() {
    return this.queue.length === 0;
  }
}

class OptimizedDijkstra {
  constructor(graph) {
    this.graph = graph;
  }
  
  findShortestPath(start, end) {
    const distances = new Map();
    const previous = new Map();
    const pq = new PriorityQueue();
    
    // 初始化
    const vertices = this.graph.getVertices();
    for (const vertex of vertices) {
      distances.set(vertex, Infinity);
    }
    distances.set(start, 0);
    pq.enqueue(start, 0);
    
    while (!pq.isEmpty()) {
      const current = pq.dequeue();
      
      if (current === end) break;
      
      const neighbors = this.graph.getNeighbors(current);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const weight = neighbor.weight || 1;
        
        const newDistance = distances.get(current) + weight;
        if (newDistance < distances.get(neighborVertex)) {
          distances.set(neighborVertex, newDistance);
          previous.set(neighborVertex, current);
          pq.enqueue(neighborVertex, newDistance);
        }
      }
    }
    
    return this.reconstructPath(previous, start, end, distances);
  }
}

// Bellman-Ford 算法
class BellmanFord {
  constructor(graph) {
    this.graph = graph;
  }
  
  findShortestPath(start, end) {
    const distances = new Map();
    const previous = new Map();
    
    // 初始化
    const vertices = this.graph.getVertices();
    for (const vertex of vertices) {
      distances.set(vertex, Infinity);
    }
    distances.set(start, 0);
    
    // 进行 V-1 次松弛
    for (let i = 0; i < vertices.length - 1; i++) {
      let updated = false;
      
      for (const vertex of vertices) {
        const neighbors = this.graph.getNeighbors(vertex);
        for (const neighbor of neighbors) {
          const neighborVertex = neighbor.to || neighbor.vertex;
          const weight = neighbor.weight || 1;
          
          const newDistance = distances.get(vertex) + weight;
          if (newDistance < distances.get(neighborVertex)) {
            distances.set(neighborVertex, newDistance);
            previous.set(neighborVertex, vertex);
            updated = true;
          }
        }
      }
      
      // 如果没有更新，可以提前结束
      if (!updated) break;
    }
    
    // 检查负权环
    if (this.hasNegativeCycle(distances)) {
      throw new Error('图中存在负权环');
    }
    
    return this.reconstructPath(previous, start, end, distances);
  }
  
  // 检测负权环
  hasNegativeCycle(distances) {
    const vertices = this.graph.getVertices();
    
    for (const vertex of vertices) {
      const neighbors = this.graph.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const weight = neighbor.weight || 1;
        
        const newDistance = distances.get(vertex) + weight;
        if (newDistance < distances.get(neighborVertex)) {
          return true; // 存在负权环
        }
      }
    }
    
    return false;
  }
  
  // 重建路径
  reconstructPath(previous, start, end, distances) {
    if (distances.get(end) === Infinity) {
      return null;
    }
    
    const path = [];
    let current = end;
    
    while (current !== null) {
      path.unshift(current);
      current = previous.get(current);
    }
    
    return {
      path: path,
      distance: distances.get(end)
    };
  }
}

// Floyd-Warshall 算法
class FloydWarshall {
  constructor(graph) {
    this.graph = graph;
    this.vertices = graph.getVertices();
    this.n = this.vertices.length;
  }
  
  // 找到所有顶点对之间的最短路径
  findAllPairsShortestPaths() {
    // 初始化距离矩阵和路径矩阵
    const distances = Array(this.n).fill().map(() => Array(this.n).fill(Infinity));
    const next = Array(this.n).fill().map(() => Array(this.n).fill(null));
    
    // 设置对角线为0
    for (let i = 0; i < this.n; i++) {
      distances[i][i] = 0;
    }
    
    // 设置直接相连的边
    for (let i = 0; i < this.n; i++) {
      const vertex = this.vertices[i];
      const neighbors = this.graph.getNeighbors(vertex);
      
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const j = this.vertices.indexOf(neighborVertex);
        const weight = neighbor.weight || 1;
        
        distances[i][j] = weight;
        next[i][j] = j;
      }
    }
    
    // Floyd-Warshall 核心算法
    for (let k = 0; k < this.n; k++) {
      for (let i = 0; i < this.n; i++) {
        for (let j = 0; j < this.n; j++) {
          if (distances[i][k] + distances[k][j] < distances[i][j]) {
            distances[i][j] = distances[i][k] + distances[k][j];
            next[i][j] = next[i][k];
          }
        }
      }
    }
    
    // 检查负权环
    for (let i = 0; i < this.n; i++) {
      if (distances[i][i] < 0) {
        throw new Error('图中存在负权环');
      }
    }
    
    return { distances, next };
  }
  
  // 重建路径
  reconstructPath(next, start, end) {
    const startIndex = this.vertices.indexOf(start);
    const endIndex = this.vertices.indexOf(end);
    
    if (next[startIndex][endIndex] === null) {
      return null; // 不可达
    }
    
    const path = [start];
    let current = startIndex;
    
    while (current !== endIndex) {
      current = next[current][endIndex];
      path.push(this.vertices[current]);
    }
    
    return path;
  }
  
  // 获取两点间的最短距离
  getShortestDistance(distances, start, end) {
    const startIndex = this.vertices.indexOf(start);
    const endIndex = this.vertices.indexOf(end);
    return distances[startIndex][endIndex];
  }
}

// A* 算法
class AStar {
  constructor(graph, heuristic) {
    this.graph = graph;
    this.heuristic = heuristic; // 启发式函数
  }
  
  findShortestPath(start, end) {
    const openSet = [start];
    const cameFrom = new Map();
    const gScore = new Map(); // 从起点到当前点的实际距离
    const fScore = new Map(); // gScore + 启发式估计
    
    // 初始化
    gScore.set(start, 0);
    fScore.set(start, this.heuristic(start, end));
    
    while (openSet.length > 0) {
      // 找到 fScore 最小的节点
      let current = openSet.reduce((min, vertex) => {
        const f1 = fScore.get(vertex) || Infinity;
        const f2 = fScore.get(min) || Infinity;
        return f1 < f2 ? vertex : min;
      });
      
      if (current === end) {
        return this.reconstructPath(cameFrom, current);
      }
      
      openSet.splice(openSet.indexOf(current), 1);
      
      const neighbors = this.graph.getNeighbors(current);
      for (const neighbor of neighbors) {
        const neighborVertex = neighbor.to || neighbor.vertex;
        const weight = neighbor.weight || 1;
        
        const tentativeGScore = (gScore.get(current) || Infinity) + weight;
        
        if (tentativeGScore < (gScore.get(neighborVertex) || Infinity)) {
          cameFrom.set(neighborVertex, current);
          gScore.set(neighborVertex, tentativeGScore);
          fScore.set(neighborVertex, tentativeGScore + this.heuristic(neighborVertex, end));
          
          if (!openSet.includes(neighborVertex)) {
            openSet.push(neighborVertex);
          }
        }
      }
    }
    
    return null; // 没有找到路径
  }
  
  // 重建路径
  reconstructPath(cameFrom, current) {
    const path = [current];
    
    while (cameFrom.has(current)) {
      current = cameFrom.get(current);
      path.unshift(current);
    }
    
    return path;
  }
}

// 常用的启发式函数
const heuristics = {
  // 曼哈顿距离（适用于网格）
  manhattan: (pos1, pos2) => {
    return Math.abs(pos1[0] - pos2[0]) + Math.abs(pos1[1] - pos2[1]);
  },
  
  // 欧几里得距离
  euclidean: (pos1, pos2) => {
    const dx = pos1[0] - pos2[0];
    const dy = pos1[1] - pos2[1];
    return Math.sqrt(dx * dx + dy * dy);
  },
  
  // 切比雪夫距离
  chebyshev: (pos1, pos2) => {
    return Math.max(Math.abs(pos1[0] - pos2[0]), Math.abs(pos1[1] - pos2[1]));
  }
};

// 导航系统
class NavigationSystem {
  constructor() {
    this.locations = new Map();
    this.roads = [];
  }
  
  // 添加地点
  addLocation(id, name, coordinates) {
    this.locations.set(id, {
      id, name, coordinates
    });
  }
  
  // 添加道路
  addRoad(from, to, distance, time) {
    this.roads.push({
      from, to, distance, time
    });
  }
  
  // 构建图
  buildGraph() {
    const graph = new AdjacencyList();
    
    for (const road of this.roads) {
      graph.addEdge(road.from, road.to, road.distance);
    }
    
    return graph;
  }
  
  // 按距离找最短路径
  findShortestPathByDistance(start, end) {
    const graph = this.buildGraph();
    const dijkstra = new Dijkstra(graph);
    return dijkstra.findShortestPath(start, end);
  }
  
  // 按时间找最短路径
  findShortestPathByTime(start, end) {
    const graph = new AdjacencyList();
    
    for (const road of this.roads) {
      graph.addEdge(road.from, road.to, road.time);
    }
    
    const dijkstra = new Dijkstra(graph);
    return dijkstra.findShortestPath(start, end);
  }
  
  // 多目标路径规划
  findMultiDestinationPath(start, destinations) {
    const graph = this.buildGraph();
    const floydWarshall = new FloydWarshall(graph);
    const { distances } = floydWarshall.findAllPairsShortestPaths();
    
    // 使用贪心算法找近似最优解
    let current = start;
    const unvisited = new Set(destinations);
    const path = [start];
    let totalDistance = 0;
    
    while (unvisited.size > 0) {
      let nearest = null;
      let minDistance = Infinity;
      
      for (const dest of unvisited) {
        const distance = floydWarshall.getShortestDistance(distances, current, dest);
        if (distance < minDistance) {
          minDistance = distance;
          nearest = dest;
        }
      }
      
      if (nearest) {
        path.push(nearest);
        totalDistance += minDistance;
        current = nearest;
        unvisited.delete(nearest);
      }
    }
    
    return { path, totalDistance };
  }
}

// 网络路由系统
class NetworkRouter {
  constructor() {
    this.nodes = new Map();
    this.links = [];
  }
  
  // 添加网络节点
  addNode(id, type, capacity) {
    this.nodes.set(id, {
      id, type, capacity, status: 'active'
    });
  }
  
  // 添加网络链接
  addLink(from, to, bandwidth, latency) {
    this.links.push({
      from, to, bandwidth, latency, status: 'active'
    });
  }
  
  // 构建网络图
  buildNetworkGraph() {
    const graph = new AdjacencyList();
    
    for (const link of this.links) {
      if (link.status === 'active') {
        // 使用延迟作为权重
        graph.addEdge(link.from, link.to, link.latency);
      }
    }
    
    return graph;
  }
  
  // 找最低延迟路径
  findLowestLatencyPath(start, end) {
    const graph = this.buildNetworkGraph();
    const dijkstra = new Dijkstra(graph);
    return dijkstra.findShortestPath(start, end);
  }
  
  // 找最高带宽路径
  findHighestBandwidthPath(start, end) {
    const graph = new AdjacencyList();
    
    for (const link of this.links) {
      if (link.status === 'active') {
        // 使用带宽的倒数作为权重（带宽越大，权重越小）
        graph.addEdge(link.from, link.to, 1 / link.bandwidth);
      }
    }
    
    const dijkstra = new Dijkstra(graph);
    const result = dijkstra.findShortestPath(start, end);
    
    if (result) {
      // 计算实际带宽（路径上最小带宽）
      let minBandwidth = Infinity;
      for (let i = 0; i < result.path.length - 1; i++) {
        const from = result.path[i];
        const to = result.path[i + 1];
        
        for (const link of this.links) {
          if ((link.from === from && link.to === to) || 
              (link.from === to && link.to === from)) {
            minBandwidth = Math.min(minBandwidth, link.bandwidth);
            break;
          }
        }
      }
      
      result.bandwidth = minBandwidth;
    }
    
    return result;
  }
  
  // 负载均衡路由
  findLoadBalancedPath(start, end, currentLoads) {
    const graph = new AdjacencyList();
    
    for (const link of this.links) {
      if (link.status === 'active') {
        // 考虑当前负载的权重
        const loadFactor = (currentLoads.get(link.from) || 0) + 
                          (currentLoads.get(link.to) || 0);
        const weight = link.latency * (1 + loadFactor * 0.1);
        graph.addEdge(link.from, link.to, weight);
      }
    }
    
    const dijkstra = new Dijkstra(graph);
    return dijkstra.findShortestPath(start, end);
  }
}

// 游戏AI路径规划
class GamePathFinder {
  constructor(gameMap) {
    this.map = gameMap;
    this.rows = gameMap.length;
    this.cols = gameMap[0].length;
  }
  
  // 构建游戏地图图
  buildGameGraph() {
    const graph = new AdjacencyList();
    
    for (let row = 0; row < this.rows; row++) {
      for (let col = 0; col < this.cols; col++) {
        if (this.map[row][col] !== '#') {
          const vertex = `${row},${col}`;
          graph.addVertex(vertex);
          
          // 添加相邻的可行走格子
          const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
          for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (this.isValid(newRow, newCol)) {
              const neighbor = `${newRow},${newCol}`;
              graph.addEdge(vertex, neighbor, 1);
            }
          }
        }
      }
    }
    
    return graph;
  }
  
  // 检查位置是否有效
  isValid(row, col) {
    return row >= 0 && row < this.rows && 
           col >= 0 && col < this.cols && 
           this.map[row][col] !== '#';
  }
  
  // 使用A*算法找路径
  findPathAStar(start, end) {
    const graph = this.buildGameGraph();
    const startVertex = `${start[0]},${start[1]}`;
    const endVertex = `${end[0]},${end[1]}`;
    
    const aStar = new AStar(graph, heuristics.manhattan);
    const path = aStar.findShortestPath(startVertex, endVertex);
    
    if (path) {
      return path.map(vertex => {
        const [row, col] = vertex.split(',').map(Number);
        return [row, col];
      });
    }
    
    return null;
  }
  
  // 考虑敌人位置的路径规划
  findSafePath(start, end, enemies) {
    const graph = this.buildGameGraph();
    
    // 为每个顶点计算危险度
    for (const vertex of graph.getVertices()) {
      const [row, col] = vertex.split(',').map(Number);
      let dangerLevel = 0;
      
      for (const enemy of enemies) {
        const distance = Math.abs(row - enemy[0]) + Math.abs(col - enemy[1]);
        if (distance <= 3) { // 敌人视野范围
          dangerLevel += (4 - distance) * 10; // 距离越近危险度越高
        }
      }
      
      // 更新边的权重
      const neighbors = graph.getNeighbors(vertex);
      for (const neighbor of neighbors) {
        neighbor.weight = 1 + dangerLevel;
      }
    }
    
    const dijkstra = new Dijkstra(graph);
    const startVertex = `${start[0]},${start[1]}`;
    const endVertex = `${end[0]},${end[1]}`;
    
    const result = dijkstra.findShortestPath(startVertex, endVertex);
    
    if (result) {
      return {
        path: result.path.map(vertex => {
          const [row, col] = vertex.split(',').map(Number);
          return [row, col];
        }),
        distance: result.distance
      };
    }
    
    return null;
  }
}

// 算法时间复杂度比较
const timeComplexity = {
  "Dijkstra": {
    "基本实现": "O(V²)",
    "优先队列优化": "O((V + E) log V)",
    "斐波那契堆": "O(V log V + E)"
  },
  "Bellman-Ford": "O(VE)",
  "Floyd-Warshall": "O(V³)",
  "A*": "O(b^d)" // b是分支因子，d是解的深度
};

console.log("最短路径算法时间复杂度:");
console.log(JSON.stringify(timeComplexity, null, 2));

// 算法选择指南
function chooseShortestPathAlgorithm(graph, requirements) {
  const recommendations = {
    "无负权边": "Dijkstra",
    "有负权边": "Bellman-Ford",
    "所有顶点对": "Floyd-Warshall",
    "启发式搜索": "A*",
    "网格地图": "A*",
    "实时计算": "Dijkstra (优先队列优化)",
    "预处理": "Floyd-Warshall"
  };
  
  return recommendations[requirements] || "根据具体需求选择";
}

// 双向Dijkstra
function bidirectionalDijkstra(graph, start, end) {
  const forwardDistances = new Map();
  const backwardDistances = new Map();
  const forwardPrevious = new Map();
  const backwardPrevious = new Map();
  
  // 初始化
  const vertices = graph.getVertices();
  for (const vertex of vertices) {
    forwardDistances.set(vertex, Infinity);
    backwardDistances.set(vertex, Infinity);
  }
  forwardDistances.set(start, 0);
  backwardDistances.set(end, 0);
  
  const forwardQueue = [{ vertex: start, distance: 0 }];
  const backwardQueue = [{ vertex: end, distance: 0 }];
  
  let meetingPoint = null;
  let shortestDistance = Infinity;
  
  while (forwardQueue.length > 0 && backwardQueue.length > 0) {
    // 从起点扩展
    const { vertex: current, distance } = forwardQueue.shift();
    
    if (backwardDistances.get(current) !== Infinity) {
      const totalDistance = distance + backwardDistances.get(current);
      if (totalDistance < shortestDistance) {
        shortestDistance = totalDistance;
        meetingPoint = current;
      }
    }
    
    // 继续扩展...
  }
  
  return reconstructBidirectionalPath(meetingPoint, forwardPrevious, backwardPrevious);
}

// 分层Dijkstra（适用于大规模图）
class HierarchicalDijkstra {
  constructor(graph) {
    this.graph = graph;
    this.hierarchy = this.buildHierarchy();
  }
  
  // 构建层次结构
  buildHierarchy() {
    // 将图分为多个层次
    // 高层包含主要节点，低层包含详细节点
    // 这里简化处理
    return {
      high: this.selectHighLevelNodes(),
      low: this.graph.getVertices()
    };
  }
  
  // 分层搜索
  findPath(start, end) {
    // 先在高层找粗略路径
    const highLevelPath = this.findHighLevelPath(start, end);
    
    // 再在低层细化路径
    return this.refinePath(highLevelPath);
  }
}