(本文未经许可禁止转载)

           

  1. 红黑树 = 234树 = Set<k> = Dictionary<k,v>

  1. Dijkstra=起点0其它点∞、循环:【找未查中最小点、标记为已查、累加边权min更新邻接点、若更新则记录上一点】、逆向输出上一点。

    • 边:<int:length>[][]
    • 点:<int:distance,int:lastid,bool:found>[]

      Dijkstra假设了所有边权非负 O(|E|+|V|log|V|)(此复杂度有Sparse假设)

  2. Bellman-Ford=起点0其它点∞、无更新为止遍历所有点:【若当前点∞跳过、累加边权min更新邻接点、若更新则记录上一点】、逆向输出上一点。

    • 边:<int:length>[][]
    • 点:<int:distance,int:lastid>[]

      Bellman ford支持负边,但比Dijkstra时间复杂度高 O(|E||V|)(此复杂度有Sparse假设)
      或者干脆不判断是否更新,直接进行|V|-1次循环(同时避免负权环死循环)。参考>>>
      可以记录更新的点作为下一次松弛候选(SPFA)

  3. SPFA=初始点放入队列、循环:【队列中取点、累加边权min更新邻接点、对于“严格”更新成功的邻接点、若不在队列中则放入队列】

    术语:“严格、非严格更新”只在本文中使用:
    严格更新:if(a>b) //success;
    非严格更新:if(a>=b) //success;

  4. Floyd=按顺序三层循环k,i,j:【a[i][j] min= a[i][k] + a[k][j];

    • 边:<int:length>[][]
  5. 最小生成树(MST)=创建点UF、小到大遍历边权:【边两点不在同集时Union】、输出UF。

    • 边:<int:length>[][]
    • UF:<int:setid>[]

网络流

基本假设:源入度=0、汇出度=0

  1. 最大流问题(Endmonds-Karp)=流量分配全部设0、循环:【BFS寻增广路更新流量分配】

    • 边:<int:capacity>[][]

    最大流问题:有向赋权(容量)图中寻找源汇间最大流量分布
    残量网络:描述流量和容量之间的可调整关系的网络
    (正向:容量分布-流量分布 反向:流量分布 )反向边解释
    例如:A==1/3==>B的残量网络为:A==2==>B & A<==1==B
    增广路:残量网络中的一条路径
    增广路定理:若源汇间无增广路,则流量分布达到最大。

  2. 最小费用最大流问题=流量分配全部设0、循环:【Bellman-Ford寻最小费用增广路更新流量分配】

    费用残量网络:描述费用调整关系的网络
    例如:A--1/3 $5-->B的费用残量网络为:A== 2*$5 ==>B & A<== -1*$5 ==B
    即:增广时花钱、反增广时退钱。所以有负权,要用Bellman-Ford
    费用增广路:费用残量网络中的一条路径

       

(本文未经许可禁止转载)

   

发表评论