图的最短路径

只是个人的总结, 防止忘记

定义: 找到一个点到另一个顶点成本最小的路径

Dijkstra( 权重非负, 有无环都可)

能够得到最短路径的算法, 只要证明自己可以放松所有的边, 直到都失效为止.

对于朴素算法: 需要最终所有节点都被放松过

对于有限队列优化的: 优先级最小的顶点的distTo[]值就是最短路径的权重, 它不会小于任意已经放松过的任意顶点的最短路径的权重, 也不会大于任何还未被放松过的任意顶点的最短路径的权重. 这样, 所有s可以到达的顶点的最短路径都按照最短路径的权重顺序被放松.

如果没有环, 那可以用拓扑排序优化, 先拓扑排序, 然后按照顺序放松节点, 这是无环最优化的, 且可以处理负权重边.

可以做的leetcode题目

(https://leetcode-cn.com/problems/path-with-maximum-probability/)

(https://leetcode-cn.com/problems/path-with-minimum-effort/)

(https://leetcode-cn.com/problems/network-delay-time/)

Dijkstra像是 BFS 和 PRIM 算法.

朴素的Dijkstra:

会放松所有的边, ans里的节点都会被访问到. 且可以看到一个节点的距离值可以被多次修改.

 // 3. dijkstra
  def dijkstraSolution(times: Array[Array[Int]], n:Int, k:Int): Int = {
    import scala.collection.mutable
    val tu = mutable.Map[Int, mutable.Map[Int, Int]]()
    (1 to n).foreach{ i => tu.put(i, mutable.Map[Int, Int]())}
    times.foreach{
      case Array(uid, vid, weight) => {
        tu(uid).put(vid, weight)
      }
    }
    val ans = mutable.Map[Int, Int]((1 to n).map( _ -> Integer.MAX_VALUE):_*) // 这个, ans的元素综合为n个和88行, 保证了全部能被访问到
    ans.update(k, 0)

    val visitedSet = mutable.Set[Int]()
    while(visitedSet.size != n) {
      val _@(miniNode, miniWeight): (Int, Int) = ans.filterNot(e => visitedSet.contains(e._1)).minBy(_._2)
      visitedSet.add(miniNode)
        //   println("visited: " + visitedSet.map(_.toString))
        //   println("ans" + ans.toMap)
      val adjs: mutable.Map[Int, Int] = tu(miniNode)
      adjs.foreach{
        case (adjNode, adjValue) => {
          ans(adjNode) =  math.min(adjValue + miniWeight,  ans(adjNode))
        //   ans.update(adjNode, math.min(adjValue + miniWeight,  ans(adjNode)))
        }

      }
    }

    if(ans.values.exists( _ == Integer.MAX_VALUE)) {
      -1
    }else{
      ans.values.max
    }

  }

优先队列优化的

在设置一个点的距离前, 会将所有之前放松其他边得到的可能最小距离值, 放到优先队列中.

另外, 优先队列里的元素, 是修改它的值, 还是重新压入,使得队列中存在失效的数据. 这两种方式, 前者是即时实现, 后者是lazy的延时实现.(我没太明白算法4里的这个)

  // 4. optimized dijstra
  def optimized_dijstra(times: Array[Array[Int]], n: Int, k: Int) = {
    import scala.collection.mutable
    val tu = mutable.Map[Int, mutable.Map[Int, Int]]()
    (1 to n).foreach{ i => tu.put(i, mutable.Map[Int, Int]())}
    times.foreach{
      case Array(uid, vid, weight) => {
        tu(uid).put(vid, weight)
      }
    }
    val ans = mutable.Map[Int, Int]((1 to n).map( _ -> Integer.MAX_VALUE):_*)
    implicit val tupleOrdering: Ordering[(Int, Int)] = new Ordering[(Int, Int)]{
      override def compare(x: (Int, Int), y: (Int, Int)): Int = x._1 - x._2
    }
    val updateSignalPriorityQueue = mutable.PriorityQueue[(Int, Int)]()(tupleOrdering)
    updateSignalPriorityQueue.enqueue((k,0))
      
    while(updateSignalPriorityQueue.nonEmpty) { // method1

      val _@(miniNode, updatedWeight) = updateSignalPriorityQueue.dequeue()

      // 如果没有被更新过...
      // 被更新过
      if(ans(miniNode) == Integer.MAX_VALUE || updatedWeight < ans(miniNode)) { 
    //  if( ans(miniNode) == Integer.MAX_VALUE || !visitedSet.contains(miniNode)) {
        ans(miniNode) = updatedWeight
        // visitedSet.add(miniNode)
        tu(miniNode).foreach {
          case _@(adjV, adjW) => {
            updateSignalPriorityQueue.enqueue(adjV -> (updatedWeight + adjW))  // 这个方法的复杂度和对有限队列的操作成正比, updateWeight < ans(miniNOde)保证了失效的边不会再作用, 但也是个弹出操作, 而如果在
                                                                              // 这里, 不用enqueue, 如果adjV存在于有限队列,修改它的值,并且,调整顺序, 总调整次数与弹出操作次数相同
          }
        }
      }else{
            ()
      }
    }
    if(ans.values.exists( _ == Integer.MAX_VALUE)) {
      -1
    }else{
      ans.values.max
    }
  }

确定无环的用拓扑排序优化

bfs 或者 dfs 的方式

效率不高 , 可以忽略

变种

最长路径

1. 转换视角, 非负权重图的最短路径就是 负权重值的最长路径 , 只要把原图的权重全部取反, 最后得到结果后再取反就好.
2. 改变relax函数中的不等式方向, 原来是新的权重如果小于旧的权重更新, 现在改成, 新的权重如果大于旧的则更新

两种方法都是转化了视角, 最短和最长是一对对偶.

另外, 在加权有向图(权重可能为负数) 中寻找最长路径, 已知最好的算法的复杂度也是指数级别的, 而若是有环, 则更复杂了.

并行任务调度

优先级限制下的并行任务调度定义:

1. 一组需要完成的任务和每个任务所需时间
2. 一组关于任务完成的先后次序的优先级限制

在满足此限制条件下, 在数量不限的处理器上安排这些任务, 使得任务最快完成, 且使用的处理器资源最少(可以理解为cpu不要忙等, 即给定任务要直接执行, 而不是还要再等它的前序先完成)最少.

这个问题, 可以通过"关键路径"的方法证明它和 "无环加权有向图"的最长路径 问题等价

将定义里的两个条件转换成对应的图:

image.png image.png

将任务转化成图的一条边, 边有两个点, 任务的时间就是边的权重, 而 "关键路径" 即条件二: 优先级次序 转化而来的, 关键路径之间转化的节点间也有路径, 不过权重为0 , 此外, 开始S具有0权重到任意任务的开始节点, 任意任务的结束节点有0权重到结束节点. 第二章图中的最长路径, 就是每个路径的开始节点的最长路径权重值就是它的任务开始时间.

相对最后期限下的并行任务调度

和上个情况不同的是, 多了一个限制类型: 某个任务需要在指定的时间点之前开始, 即指定和另一个任务的开始时间的相对时间. 举例: 任务2 必须在任务4 开始后的12个时间内启动.

等价为; 加权有向图(可能环以及负权重边)的最短路径问题