算法笔记 · he110

Dijkstra 最短路径算法

Dijkstra 本质上来说就是一个广度优先搜索算法。

从最基础的二叉树广度优先搜索算法开始，基本结构类似于

function bfs(root: TreeNode | null) {
  const queue: TreeNode[] = root ? [root] : []

  while (queue.length) {
    const len = queue.length
    for (let i = 0; i < len; ++i) {
      // 这里就会遍历到每个节点
      const node = queue.shift()

      // 将下一层节点入队
      if (node.left) {
        queue.push(node.left)
      }
      if (node.right) {
        queue.push(node.right)
      }
    }
  }
}

当我们将二叉树广度优先搜索算法拓展到图结构的时候，对比一下图与二叉树的差异：

二叉树的子节点数量最多 2 个；图可能有无限多个子节点。
二叉树的子节点不可能被重复访问；图的子节点可能 不止一次被访问 。
二叉树每次遍历到当个节点时，需要计算的状态都是确定并且唯一的；图由于遍历到节点的路径不同，可能会导致 需要计算的值不一致 。

一般来说，只要能解决第二点差异，不重复访问同一节点，第三点差异就不存在了。

所以一般情况下，图的广度优先搜索算法如下：

/**
 * @param graph 声明对于 ID 为 0 - n 的元素，其相邻节点都有哪些，也就是邻接表
 */
function bfs(graph: number[][], startNodeID: number) {
  const n = graph.length
  const visited = new Array(n).fill(false)
  const queue: number[] = [startNodeID]

  while (queue.length) {
    const len = queue.length

    // 这里还是用 for 循环
    // 目的是为了限制住，每次遍历外扩的时候，距离 startNode 都是相同的层数
    // 也就是默认两点之间距离相等，比如都是 1
    for (let i = 0; i < len; ++i) {
      // 这里就会遍历到每个节点
      const node = queue.shift()
      // 登记这个节点已经访问过了，不需要再重复访问
      visited[i] = true

      // 将下一层节点入队
      const children = graph[i]
      for (const nextNodeID of children) {
        // 没访问过的节点才入队，在这里限制每个节点只能访问一次
        if (!visited[nextNodeID]) {
          queue.push(nextNodeID)
        }
      }
    }
  }
}

这种广度优先搜索算法就可以抹平二叉树与图之间的结构差异，但是这种算法具有局限性。

由于第三点差异的存在，当我们计算的图，在节点之间距离不等的时候，重复遍历同一节点是有必要的。

就像坐公交车一样，一般情况下会有很多条路线，包括直达或者转线，这些线路都能到达目的地，但是到达目的地的时间却不相同。

有的虽然直达，但是需要 1 小时，有的虽然转 3 - 4 次，但是可能半小时就到了。

按照访问先后一刀切的选择线路是不可取的。

所以诞生了 Dijkstra 算法。

Dijkstra 算法的基本逻辑就是：广度优先搜索 + 剪枝

interface State {
  /** 需要访问的节点 ID */
  id: number
  /** 记录访问当前节点时，需要统计的状态值是多少，在本例中指与 startNode 之间的距离 */
  val: number
}

/**
 * Dijkstra 一般解决的是节点间 距离/代价 不相同的情况
 * 所以除了记录相邻节点有哪些，还需要记录到达这个节点的 距离/代价
 * 这里以距离为例
 * endNodeID 也可以不需要，最短路可以寻找到任意点的最短路径，也就是 lengths 数组
 */
function dijkstra(graph: [number, number][][], startNodeID: number, endNodeID: number) {
  const n = graph.length
  const max = Number.MAX_SAFE_INTEGER

  /** 初始化每个节点距离 startNode 的最短距离 */
  const lengths = new Array(n).fill(max)
  lengths[startNodeID] = 0

  /**
   * 普通广度优先搜索算法中的 queue 队列
   * 如果是有优先队列可以用的话，这里可以换出优先队列
   * 这样在第一次访问到终点时，就可以直接结束了
   * 因为优先队列会从所有 children 中取当前路径最短的那条优先遍历
   * 由于 JS 默认没有堆的结构，自己实现优先队列过于繁琐，一般算法题中不会使用
   * 这里换成普通队列也是 OK 的，只是多一些遍历次数，但是由于本身是 Edge * log(Node) 级别的算法
   * 不使用优先队列的话会回退到 Edge * log(Edge) 级别，由于都是 log 级别了，实际上开销并不会增大多少
   */
  const states: State[] = []
  states.push({
    id: startNodeID,
    val: lengths[startNodeID],
  })

  while (states.length) {
    const { id, val } = states.shift()

    // 如果有终点的话，在这里可以直接对终点剪枝了，不需要继续遍历
    // 这里还是普通队列，所以更新最短路径后剪枝即可
    if (id === endNodeID) {
      lengths[id] = Math.min(lengths[id], val)
      continue
    }

    // 如果到达这个节点时，已经需要的距离，比前面记录的最小距离还要长，那就舍弃掉这条分支，也就是剪枝
    // for 里面已经剪枝过了，但是这里还是需要继续剪枝
    // 因为节点可能被重复遍历，可能在 for 剪枝之后，在当前节点更新一个更小的 length
    // 所以这里还需要继续剪枝
    if (val > lengths[id]) {
      continue
    }

    // 遍历 children
    for (const [nextNodeID, nextNodeStep] of graph[id]) {
      // 计算到达下一个节点的距离是多少
      const length = val + nextNodeStep
      // 如果到达下一个节点的距离，比已经记录的还要长，那就没有必要遍历了，直接剪枝
      // 只有比已经记录的小，才需要遍历
      if (length < lengths[nextNodeID]) {
        // 更新 lengths 数组
        lengths[nextNodeID] = length
        // 添加到待访问队列中
        states.push({
          id: nextNodeID,
          val: length,
        })
      }
    }
  }

  // 如果节点的最小长度还是初始值，那就说明不可达，返回 -1
  return lengths[endNodeID] === max ? -1 : lengths[endNodeID]
}

散列冲突

Hash 函数在映射时，不能完全保证 A !== B 时， hash(A) !== hash(B) ，原因在于 hash 映射出来的容量是有限的，就像 hash(x) = x % 10 ，容量就是 10 。

当出现散列冲突时，常见有两种解决冲突的方法:

开放寻址法: 当位置被占用时，往下继续寻址，直到找到空位。相当于车位被占用了，继续往里面开，看有没有别的空车位。也就是说，我们通过引进新的冲突来规避现有的冲突。
- 查找: 根据 hash 找到地址，判断存储的值是否与查找值匹配，不匹配继续往下查找。
- 删除: 不能直接删除元素，因为可能该位置原本的节点因为被占用挪走了，只能标记为 deleted ，删除时遇到 deleted 继续往下查找。
链表法: 建立多维结构，将 hash(x) 映射为链表的头节点，所有相同 hash 的值通过链表串起来即可。