首页 > 代码库 > dijkstra(最短路)和Prim(最小生成树)下的堆优化
dijkstra(最短路)和Prim(最小生成树)下的堆优化
dijkstra(最短路)和Prim(最小生成树)下的堆优化
最小堆：
down(i)【向下调整】：从第k层的点i开始向下操作，第k层的点与第k+1层的点(如果有)进行值大小的判断，如果父节点的值大于子节点的值，则修改，并继续对第k+1层与第k+2层的点进行判断和修改，否则不修改，且退出。当点向下移动到树的最后一层，没有子节点供判断与修改，停止操作。
树最多有log(n) 层[log(n)=log2n，一般省略数字2]，时间复杂度log(n)次。
up(i)【向上调整】：同理，时间复杂度log(n)次。
1.求n个数进行排序：
I．建树(n/2次down)：
for i←n/2 downto 1 do down(i)
II．取数(n次down)：
for i←1 to n do
temp←a[1];
a[1]←a[n];
a[n]←temp;
n←n-1;
down(1);
所以时间复杂度：O(nlogn)
2.dijkstra , prim 需要修改数，取数多少次？
I．dijkstra:
从点x出发到点y(或其它剩余点)的最短路：
dist[t]：点t到点x的最短距离，若点t不能到达点x，则值为无穷(设为一个足够大的值，如2000000000)。初始时dist[x]=0，其它点dist[]=无穷。
初始：d=x。
1.遍历所有与点d相关联的边，修改与d点相邻的点的最短距离(到x点)。
2.在未执行1操作的点中找到最短距离(到x点)的点d。
3.重复1,2操作，直到2操作d=y，或者执行n-1次(总共n个点，那么求的是从x点到其它点的最短路)。
时间复杂度：
最多执行n-1次操作，而操作1,2时间复杂度O(n)，时间复杂度O(n^2)。
堆优化：
初始时，把所有的dist[k](k=1,2,……,n)建最小堆。对于操作1，修改堆中某些数(dist[])的值，并对这些数的位置进行修改(距离是越来越短，所以进行向上调整)；
对于操作2，把堆中第一个数(最小值)取出，删除根结点，把最后一个元素作为根结点，然后对根节点进行向下调整，保证调整后的根节点为树中的最小点。
时间复杂度：
建堆n个数，时间复杂度O(nlogn)
取数n-1次，而堆中节点个数总小于等于n(最多有n个dist[])，时间复杂度O(nlogn)。
最坏的情况：
如下图(可删去部分边)，与点k相邻的边(边另外的点的编号小于k)的长度为k，求从n点出发到y点，从点n出发到点1，则所有的边都会被修改为dist[]的值一次，修改e次，则时间复杂度O(eloge)，其中e为边的数目。
总时间复杂度O(nlogn+elogn)。
若图是稠密图，e很大，如n<=10000，而e<=n*(n-1)/2,若e= n*(n-1)/2，nlogn+elogn <664452058,而n*n=100000000，则该优化比原来时间复杂度还高不少。
若图是稀疏图，e不大，如n<=10000，e<=100000，则elogn<1328772，n*n=100000000，此时用该优化不会超时而用原方法会超时。
更好的优化：斐波那契堆(不涉及删除元素的操作仅需O(1)的平摊运行时间)
取数n-1次(删除+修改)，而堆中节点个数总小于等于n(最多有n个dist[])，时间复杂度O(nlogn)。
修改e次数值，时间复杂度O(e)。
总时间复杂度：O(nlogn+e)。
II．Prim：
求最小生成树
dist(t)：点t到集合S中的点的最短距离，该最短距离为其中一条边的长度，若点t不能到达任意一个点，则值为无穷(设为一个足够大的值，如2000000000)。初始时dist[x]=0，其它点dist[]=无穷。
从任意一个点x出发，初始：d=x，S=空集【S为集合】，T=全集。
1.S=S+{d},T=T-{d},遍历所有与点d相关联的边，修改集合T中的点的dist值。
2.从点T中找到dist[]值最小对应的点d，图添加一条边，该边的长度为dist[d]。可以添加一个变量记录边的另外一个点。
3.重复1,2操作，直到执行n-1次（即添加n-1条边）。
时间复杂度：最多执行n-1次操作，而操作1,2时间复杂度O(n)，时间复杂度O(n^2)。
堆优化：
初始时，把所有的dist[k](k=1,2,……,n)建最小堆。对于操作1，修改堆中某些数(dist[])的值，并对这些数的位置进行修改(距离是越来越短，所以进行向上调整)；
对于操作2，把堆中第一个数(最小值)取出，删除根结点，把最后一个元素作为根结点，然后对根节点进行向下调整，保证调整后的根节点为树中的最小点。
时间复杂度：同理总时间复杂度O(nlogn+elogn)。
斐波那契堆优化：O(nlogn+e)。
另外的方法（不一样的角度）：
dist(t)：点t到集合S中的点的最短距离，该最短距离为其中一条边的长度，若点t不能到达任意一个点，则值为无穷(设为一个足够大的值，如2000000000)。初始时dist[x]=0，其它点dist[]=无穷。
从任意一个点x出发，初始：d=x，S=空集【S为集合】，T=全集。R=空集。
1.S=S+{d},T=T-{d},遍历所有与点d相关联的边，若某条边的另外一个点在T集合而不是在S集合，则把该边加入集合R中。
2.从集合R中找到长度最小的且边有一个点在T集合(边的另外一个点必在S集合)的边，d=边的两点中的在T集合的点。图添加一条边，该边的长度为dist[d]。可以添加一个变量记录边的另外一个点。
3.重复1,2操作，直到执行n-1次（即添加n-1条边）。
堆优化：
把边加入堆中，时间复杂度O(eloge)。
取边n-1次，时间复杂度O(nloge)。
[事实上每次堆的数目小于等于e]
总时间复杂度O(nloge+eloge)。
无疑，该方法比上述方法时间复杂度要高。
dijkstra(最短路)和Prim(最小生成树)下的堆优化