使用 Fibonacci 堆的 Dijkstra 算法进行网络优化。
本文介绍了斐波那契堆数据结构，并展示了如何将其用于图优化。
引言
本文介绍了一种强大的网络优化数据结构——斐波那契堆。首先，考虑一个常见的二叉堆，其中每个节点最多有两个子节点，并且这两个子节点的值必须小于父节点。对于斐波那契堆，我们放宽了这一限制。因此，每个节点可以有任意数量的子节点。此外，斐波那契堆没有单一的根元素，而是由一组根组成，其中具有最小键的根由一个头部指针区分。
这种特殊的堆还具有不同的操作，这些操作通常不像二叉堆那样昂贵。操作 decrease_key、make_heap、insert 和 meld 可以在 O(1) 时间内完成。最耗时的操作是 delete_min，其时间复杂度为 O(log n)。
本文还将介绍斐波那契堆在更快速地实现网络优化 Dijkstra 算法中的应用。
斐波那契堆详解
首先，让我们定义一个斐波那契堆。
斐波那契堆是一种包含根元素列表的堆。堆中的每个节点都可以有任意数量的子节点。元素按堆的顺序排序：一个节点的值不应大于其任何子节点的最小值。
节点长什么样子？
堆的单个节点需要满足哪些要求？
作为对比：在二叉堆中，每个节点有 4 个指针：1 个指向父节点，2 个指向子节点，1 个指向数据。
由于斐波那契堆中子节点的数量未知，我们必须将节点的子节点组织成一个链表。因此，每个节点最多需要两个指向其兄弟节点的指针。这构成了一个线性的双向链表。现在，我们还需要一个指针指向子节点列表中的任意一个节点，以及一个指向每个节点的父节点的指针。总而言之，需要 5 个指针：
- 左兄弟
- 右兄弟
- 父节点
- 子节点
- data
此外，我们为每个节点定义一个 秩，它表示该节点有多少个子节点。
现在，考虑这些节点元素对于斐波那契堆实现所需的操作。
堆节点操作
现在，我们可以实现节点操作了。
所需的操作包括：
- AddChild
- AddSibling
- 移除
通过将其插入子节点列表并链接，向当前节点添加一个子节点。此操作可在 O(1) 时间内完成。
将一个节点添加到当前节点所属的子节点列表中。此操作也可在 O(1) 时间内完成。
从兄弟列表中移除节点并刷新受影响的指针。此操作也可在 O(1) 时间内完成。
bool Node::addChild(Node *node)
{
if(children != NULL)
children->addSibling(node);
else
{
children = node;
node->parent = this;
rank = 1;
}
return true;
}
bool Node::addSibling(Node *node)
{
Node* temp = rightMostSibling();
if(temp == NULL)
return false;
temp->rightSibling = node;
node->leftSibling = temp;
node->parent = this->parent;
node->rightSibling = NULL;
if(parent)
parent->rank++;
return true;
}
bool Node::remove()
{
if(parent)
{
parent->rank--;
if(leftSibling)
parent->children = leftSibling;
else if(rightSibling)
parent->children = rightSibling;
else
parent->children = NULL;
}
if(leftSibling)
leftSibling->rightSibling = rightSibling;
if(rightSibling)
rightSibling->leftSibling = leftSibling;
leftSibling = NULL;
rightSibling = NULL;
parent = NULL;
return true;
}
斐波那契堆操作
现在可以实现斐波那契堆了。节点树通过指向最小值的节点的特定指针来访问。该元素位于根列表中，并且没有父节点。否则，就会违反堆的顺序。
基本操作包括：
- insertNode
将一个节点插入到根列表中，并检查其值是否低于当前最小的节点，如果需要则更改访问指针。此操作的时间复杂度为 O(1)。
bool FibonacciHeap::insertVertex(Node * node)
{
if(node == NULL)
return false;
if(minRoot == NULL)
minRoot = node;
else
{
minRoot->addSibling(node);
if(minRoot->key > node->key)
minRoot = node;
}
return true;
}
减小指定节点的值。然后将该节点从其兄弟列表中移除并插入到根列表中。至少，会检查是否需要更改访问指针。此操作需要 O(1) 时间。
void FibonacciHeap::decreaseKey(double delta, Node* vertex)
{
vertex->key = delta;
if(vertex->parent != NULL) // The vertex has a parent
{
// Remove vertex and add to root list
vertex->remove();
minRoot->addSibling(vertex);
}
// Check if key is smaller than the key of minRoot
if(vertex->key < minRoot->key)
minRoot = vertex;
}
返回由访问指针引用的节点。这是具有最小键的节点。
Node* FibonacciHeap::findMin()
{
return minRoot;
}
检查根列表中的两个节点是否具有相同的秩。如果是，则将键值较大的节点移到另一个节点的子节点列表中。此步骤在 O(1) 时间内完成。
bool FibonacciHeap::link(Node* root)
{
// Insert Vertex into root list
if(rootListByRank[root->rank] == NULL)
{
rootListByRank[root->rank] = root;
return false;
}
else
{
// Link the two roots
Node* linkVertex = rootListByRank[root->rank];
rootListByRank[root->rank] = NULL;
if(root->key < linkVertex->key || root == minRoot)
{
linkVertex->remove();
root->addChild(linkVertex);
if(rootListByRank[root->rank] != NULL)
link(root);
else
rootListByRank[root->rank] = root;
}
else
{
root->remove();
linkVertex->addChild(root);
if(rootListByRank[linkVertex->rank] != NULL)
link(linkVertex);
else
rootListByRank[linkVertex->rank] = linkVertex;
}
return true;
}
}
将指向访问指针的节点的所有子节点复制到根列表中。每次插入后，如果需要，会执行一个链接步骤。至少，会删除最小元素，并确定具有最小键的节点。摊销时间取决于最小节点子节点的数量。在最坏的情况下，对于每个子节点，都需要执行移除、插入和链接操作。这需要 O(log n) 时间。
Node* FibonacciHeap::deleteMin()
{
Node *temp = minRoot->children->leftMostSibling();
Node *nextTemp = NULL;
// Adding Children to root list
while(temp != NULL)
{
nextTemp = temp->rightSibling; // Save next Sibling
temp->remove();
minRoot->addSibling(temp);
temp = nextTemp;
}
// Select the left-most sibling of minRoot
temp = minRoot->leftMostSibling();
// Remove minRoot and set it to any sibling, if there exists one
if(temp == minRoot)
{
if(minRoot->rightSibling)
temp = minRoot->rightSibling;
else
{
// Heap is obviously empty
Node* out = minRoot;
minRoot->remove();
minRoot = NULL;
return out;
}
}
Node* out = minRoot;
minRoot->remove();
minRoot = temp;
// Initialize list of roots
for(int i=0; i<100; i++)
rootListByRank[i] = NULL;
while(temp)
{
// Check if key of current vertex is smaller than the key of minRoot
if(temp->key < minRoot->key)
{
minRoot = temp;
}
nextTemp = temp->rightSibling;
link(temp);
temp = nextTemp;
}
return out;
}
现在我们已经实现了 Dijkstra 算法所需的所有必要操作，我们将在下一部分讨论。
使用斐波那契堆的 Dijkstra 算法
Dijkstra 的概念
Dijkstra 算法的工作原理如下。从目标顶点开始，它检查每个具有指向当前顶点的入边的顶点；如果经过当前顶点的路径比之前找到的路径更短，则替换它。然后，对该顶点执行相同的操作。当所有顶点都被扫描时，算法终止。这个操作称为 扫描，原因如下。
总而言之，扫描 可以通过以下步骤描述：
- 找到所有以当前节点为尾部的边的头顶点。
- 对于这些顶点中的每一个，检查是否可以通过当前顶点和它们之间的边来改进已找到的最佳路径。
Dijkstra 算法的实现
实际的 Dijkstra 算法非常简单。从源顶点开始，我们执行一次 扫描 并将该顶点标记为已扫描。然后，我们用与源顶点有边的顶点重复此步骤。然后，我们对所有具有指向最后一个扫描顶点的边的顶点重复 扫描。
在算法过程中，节点可以有三种状态：LABELED（已标记）、UNLABELED（未标记）和 SCANNED（已扫描）。当找到到目标的最近路径时，节点被标记为已标记。当尚未找到路径时（初始状态），节点未标记，当找到路径但可能存在更短路径时，节点已标记。
FibonacciHeap* heap = new FibonacciHeap();
heap->insertVertex(vertices[n-1]);
bool abort = false;
long j = 0;
// Scan
do
{
// Delete minimum path
Node* v = heap->deleteMin();
v->state = SCANNED;
for(int i = 0; i < v->incomingEdges.size(); i++)
{
Edge* currentEdge = v->incomingEdges[i];
Node* headOfCurrentEdge = currentEdge->tail;
if(headOfCurrentEdge->state != SCANNED)
{
if(headOfCurrentEdge->state == UNLABELED)
{
// Insert a vertex with infinite key
headOfCurrentEdge->state = LABELED;
headOfCurrentEdge->pred = v;
headOfCurrentEdge->key = v->key + currentEdge->length;
heap->insertVertex(headOfCurrentEdge);
}
else if(headOfCurrentEdge->key > v->key + currentEdge->length )
{
// decrease the key of a vertex with finite key
headOfCurrentEdge->pred = v;
heap->decreaseKey(v->key + currentEdge->length, headOfCurrentEdge);
}
}
}
}
while(!heap->isEmpty());
完成此算法后，我们将在 pred 指针中获得每个节点的后继节点。该指针指向到目标的最近路径的下一个顶点。结果是我们为每个顶点找到了到目标的最近路径。我们只需要沿着后继节点即可。
while(temp)
{
printf("%d", temp->data);
temp = temp->pred;
if(temp)
printf(" - ");
}
这种结构称为 最短路径树，因为它看起来像一棵以目标顶点为根的树。对于每个节点，通过在该树中的后继节点来获得父节点。