2

我正在尝试实现 Dijkstra 算法。

 foreach distance d
   d = INFINITY
 d[source] = 0

 create_heap_based_on_Distances();

 while(true)
   bestedge = heap[0]

   remove_minimum_from_heap //it will be heap[0]

   foreach adjacency of bestedge
      if (weight + bestedge_distance < current_distance)
      {
          current_distance = weight + bestedge_distance

          // Now I have to update heap, how can I do that?
      }
   if (heap_empty) break

那么，在放松的时候，我怎样才能更新堆，所以它会有正确的顺序？在该步骤中，我没有该节点的堆索引。这是否意味着我必须创建一个新数组nodes[edge] = heapIndex，这样我才能获得该节点的堆索引？insert_to_heap但它似乎非常低效，因为我需要更新remove_minimum功能。

C 或 JAVA 代码都可以。

4

2 回答 2

4

这是否意味着我必须创建一个像nodes[edge] = heapIndex 这样的新数组，这样我才能获得该节点的堆索引？

是的。

但它似乎非常低效，因为我需要更新 insert_to_heap、remove_minimum 函数。

数组更新在理论上和实践中都非常便宜，而且每次堆操作只需要执行其中的一些操作，因此这根本不是低效的。此外，与图数据结构的存储成本相比，这种数组的内存使用非常便宜。

于 2013-04-25T14:40:19.997 回答
0 
Does that mean I have to create a new array like nodes[edge] = heapIndex, 
so I could get a heap's index for that node?

我不知道节点 [edge] 的确切含义。在我看来，它应该是一个 f[node]=HeapIndex 的 Map（确实是一个数组）f（它给出了该节点在 Heap 中的索引）。node[edge] 的存储效率不高。

那么如何实现MapHeap呢？我已经实现了一个高效的 MapHeap，但在代码中没有太多注释：

template<class DT>
struct MapHeap
{
    DT f[HEAP_SIZE+5];//store the distance
    int mp1[HEAP_SIZE+5];//val -> index
    // I assume the val is unique.
    // In the dijk, the val is the nodeId,so it must be unique. 
    // mp1[nodeId] gives the index of that node in my heap
    int mp2[HEAP_SIZE+5];//index -> val
    int nv;// number of node in my heap now
    MapHeap():nv(0)
    {
        memset(mp1,-1,sizeof(mp1));
        memset(mp2,-1,sizeof(mp2));
    }
    void print(int n)
    {
        for(int i=1;i<=n;i++) printf("%d ",f[i]);
        puts("");
        for(int i=1;i<=n;i++) printf("%d ",mp1[i]);
        puts("");
        for(int i=1;i<=n;i++) printf("%d ",mp2[i]);
        puts("");
    }
    void print(){print(nv);}
    bool resize(int n)
    {
        if (nv<0||nv>HEAP_SIZE) return 0;
        for(int i=n+1;i<=nv;i++)
        {
            mp1[mp2[i]]=-1;
            mp2[i]=-1;
        }
        nv=n;
        return 1;
    }
    DT top()//get the smallest element
    {
        if (nv<1) return DT(-1);
        return f[1];
    }
    DT get(int idx)
    {
        if (idx<1||idx>nv) return DT(-1);
        return f[idx];
    }
    // it's for unpdating the heap. It should be pravite method. 
    // Because I write this code for competition, so I just ignore the accsee controling
    void movedown(int now,int val,const DT &x)//this node is larger than son
    {
        for(;now*2<=nv;)
        {
            int a=now*2;
            int b=now*2+1;
            if (b<=nv&&f[b]<f[a]) a=b;
            if (f[a]>=x) break;
            f[now]=f[a];
            mp1[mp2[a]]=now;
            mp2[now]=mp2[a];
            now=a;
        }
        f[now]=x;
        mp1[val]=now;
        mp2[now]=val;
    }
    void moveup(int now,int val,const DT &x)//this node is smaller than father
    {
        for(;now>1;now>>=1)
        {
            int par=now>>1;
            if (f[par]<=x) break;
            f[now]=f[par];
            mp1[mp2[par]]=now;
            mp2[now]=mp2[par];
        }
        f[now]=x;
        mp1[val]=now;
        mp2[now]=val;
    }
    bool pop(int idx=1)//pop a element, pop the smallest element by default
    {
        if (idx<1||idx>nv) return 0;
        DT &x=f[nv];
        int v1=mp2[nv];
        int v2=mp2[idx];
        mp1[v1]=idx;
        mp2[idx]=v1;
        mp1[v2]=-1;
        mp2[nv]=-1;
        nv--;
        if (idx!=nv+1) movedown(idx,v1,x);
        x=0;
        return 1;
    }
    bool push(const DT &x,int val)//push a node, and with the value of val(in dijk, the val is the nodeId of that node)
    {
        int now=++nv;
        if (now>HEAP_SIZE) return 0;
        moveup(now,val,x);
        return 1;
    }
};
于 2013-04-25T16:18:13.950 回答