常用的最短路算法总结

2023/8/2

• dijstra，每次并入一个节点并更新dist值，下面列举几种不同实现方式
  • 邻接矩阵 时间复杂度为O(v^2)
  • 邻接链表，每个顶点连着跟他相连的顶点作为链表中的节点，存储着目的顶点和边的权重，时间复杂度为O(Elogv) 可以用list<pair<int(目的顶点),int(边的权重)>>
    • 最小堆
      • 基本知识：最小堆是一个完全二叉树，节点值由一个数组维护，每个左右子树的父节点的值都比子节点的值小
      • 构建最小堆：完全二叉树的非叶子节点数量为[N/2]，N为节点数量

        证明：
        设出度数为0，1，2的节点数分别为x, y, z，由完全二叉树的性质可知，y为0(N为奇数)或1(N为偶数)，且有以下公式：
        x + y + z = N, 2x + y = N - 1(边的数量，除了头节点每个节点都被一条边牵引)
        则可得出 x + y = N / 2(向下取整)

        构建堆时叶子节点由于没用子节点，我们可以将其认为是已经构建好的子堆，那我们可以从最后一个非叶子节点开始以此执行下沉操作, 总时间复杂度为O(N)
      • 下沉：递归比较父节点和左右子节点中较大节点的值，若小于，则交换, 时间复杂度为O(logN)
      • 上浮：递归比较要操作的子节点和父节点中较大节点的值，若小于，则交换，时间复杂度为O(logN)
      • 提取最小值/删除操作：将堆中最小值节点，也就是根节点和数组中最后一个节点调换位置，并减少堆中size的值，之后进行堆化操作
      • 插入元素：在数组末尾新增元素，并执行上浮操作
      • 减少键值：减小堆中某个节点的值(直接在数组中针对索引进行操作)，由于是减小了键值所以之后执行上浮操作
      • STL中实现的priority_queue默认实现最大堆，和最小堆完全相反，其父节点的值要大于左右子树的值
  • stl set : 集合的定义，每个元素只有一份在集合中
  • std::tie是C++标准库中的一个函数模板，位于头文件中。std::tie用于创建一个std::tuple元组，可以用来绑定多个变量，并从中提取元素值。
  • std::tie的用法是将多个变量作为参数传递给它，并返回一个元组，其中包含这些变量的引用。可以使用std::tie来简洁地同时解包多个变量。
  • myset.erase(myset.find(40)); 只删除第一个匹配到的元素，而 myset.erase(40); 会删除所有匹配到的元素。
  • set的默认排序方式为升序排序，priority_queue相反
  • std::sort(myints, myints+8, myfunction/myobject(strcut or class仿函数)) / std::set<int, less/greater/myfunctionobject/bool(*)(int, int)> myset(myfunction)
  • pair的默认排序方式按pair.first排序
  • 常见的实现方法为BFS，每次从队列或集合中取出最小的dist所对应的节点，松弛该节点相连的所有边，若有更新，将更新后的pair加入至队列中
  • 为了防止遍历到已经提取出最小值的节点，可以加入vis数组，但加不加无所谓，最终都会收敛至最小值

2023/8/3

• 原地哈希：将原数组的元素对应到其下标中，比如1对应的下标为1-1=0，还可以使用替换的方式将0索引上的数字与1进行交换，该方式可以用来查看某个数字是否出现在了数组中。