lecture 10.23

1. Prim's Algorithm时间复杂度:找到最小edge O(V*E)

利用priority queue找最小edge时,O(V*logE)

2. priority queue: 有的queue需要按照一定顺序输出,而不是queue默认的先进先出原则(FIFO)

join: O(1)

leave: O(N)  遍历所有找到符合条件的

#利用heap,则join,leave均为O(logN)

3. shortest path

大于0;

结果不唯一;

可分为single-source(SSSP), all-pairs(APSP)

4. SSSP

pred[]记录是经由哪个点过来的

#edge relaxation: 在dist[]里记录已知的最短cost,逐渐update

支持算法:Dijkstra's Algorithm

a) 将初始点的举例设为0,其他设为无穷大

b) 将所有未确定shortest path的点放在set里面,检测从起始点出发的edges,并记录其weight

c) 将起始点从set中删除,从起始点到达的第一个点开始,继续观察从它出发的edges,若是小于已知距离替换并记录

d) 直至set为空

lecture 10.23

 

 

lecture 10.23

 

cost: O(E+V^2)=O(V^2)

利用PQueue可以变成O(E+V*logV)

5. APSP

支持算法:Floyd's Algorithm(也被称为Floyed-Warshall Algorithm)

lecture 10.23

 lecture 10.23

 

三层循环,故O(V^3)

6. network flow

类比从工厂向仓库分别通过多种途径运输货物,每条路径可以承载的货物量不同

对于每一个vertex,流进的flow与流出的flow数目要相同

 

 lecture 10.23

 

residual network

 lecture 10.23

 

支持算法:Edmonds-Karp Algorithm

找到最短augumenting path,更新residual network,找到新的augumenting path,更新。。。

lecture 10.23

 

O(V*E^2)

 

上一篇:Lecture 19: Bias


下一篇:lecture 7