dijkstra算法实现 - decoqt/mywiki GitHub Wiki

#Dijkstra算法实现

##Fibonacci ##Heap

###松弛技术RELAX的介绍 Dijkstra 算法使用了松弛技术，对每个顶点v<-V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径的估计。

首先，得用O（V）的时间，来对最短路径的估计，和对前驱进行初始化工作。 INITIALIZE-SINGLE-SOURCE(G, s)

for each vertex v ∈ V[G]
	do d[v] ← ∞
		π[v] ← NIL      //O（V）
d[s]=0

RELAX(u, v, w)

if d[v] > d[u] + w(u, v)
	then d[v] ← d[u] + w(u, v)
		π[v] ← u        //O（E）

Dijkstra 算法

此Dijkstra 算法分三个步骤:

INSERT (第3行),
EXTRACT-MIN (第5行),
DECREASE-KEY(第8行的RELAX，调用此减小关键字的操作)。

DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s) //对每个顶点初始化，O(V)
2 S ← Ø
3 Q ← V[G] //INSERT，O(1)
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //简单的O(VV)；二叉/项堆，和FIB-HEAP的话，则都为O(VlgV)。
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //简单方式:O(E)，二叉/项堆，EO(lgV)，FIB-HEAP，EO(1)。

###Dijkstra 算法的运行时间在继续阐述之前，得先声明一个问题，DIJKSTRA（G，w，s）算法中的第5行，EXTRACT-MIN(Q)，最小优先队列的具体实现。而Dijkstra 算法的运行时间，则与此最小优先队列的采取何种具体实现，有关。

最小优先队列三种实现方法：

利用从1至|V| 编好号的顶点，简单地将每一个d[v]存入一个数组中对应的第v项，如上述DIJKSTRA（G，w，s）所示，Dijkstra 算法的运行时间为O(V^2+E)。
如果是二叉/项堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(VlgV)，所以，Dijkstra 算法的运行时间为O(VlgV+E*lgV)，若所有顶点都是从源点可达的话，O（(V+E)lgV）=O（ElgV）。当是稀疏图时，则E=O(V^2/lgV)，此Dijkstra 算法的运行时间为O(V^2)。
采用斐波那契堆实现最小优先队列的话，EXTRACT-MIN(Q)的运行时间为O(VlgV)，所以，此Dijkstra 算法的运行时间即为O(VlgV+E)。

综上所述，此最小优先队列的三种实现方法比较如下
EXTRACT-MIN + RELAX

简单方式： O（VV + E1）
二叉/项堆： O（V*lgV + |E|lgV）
源点可达：O（ElgV）
稀疏图时，有E=O（V^2/lgV） => O（V^2）
斐波那契堆：O（V*lgV + E）

当|V|<<|E|时，采用DIJKSTRA（G，w，s）+ FIB-HEAP-EXTRACT-MIN(Q)，即斐波那契堆实现最小优先队列的话，优势就体现出来了。

###斐波那契堆实现最小优先队列由以上内容，我们已经知道，用斐波那契堆来实现最小优先队列，可以将运行时间提升到O（VlgV+E）。|V|个EXTRACT-MIN 操作，每个平摊代价为O（lgV），|E|个DECREASE-KEY操作的每个平摊时间为O（1）。

先直接给出Dijkstra 算法 + FIB-HEAP-EXTRACT-MIN(H)的算法： DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S ← Ø
3 Q ← V[G] //第3行，INSERT操作，O（1）
4 while Q ≠ Ø
5 do u ← EXTRACT-MIN(Q) //第5行，EXTRACT-MIN操作，VlgV
6 S ← S ∪{u}
7 for each vertex v ∈ Adj[u]
8 do RELAX(u, v, w) //第8行，RELAX操作，EO(1)

FIB-HEAP-EXTRACT-MIN(H) //平摊代价为O（lgV）
1 z ← min[H]
2 if z ≠ NIL
3 then for each child x of z
4 do add x to the root list of H
5 p[x] ← NIL
6 remove z from the root list of H
7 if z = right[z]
8 then min[H] ← NIL
9 else min[H] ← right[z]
10 CONSOLIDATE(H)
11 n[H] ← n[H] - 1
12 return z

####Dijkstra 算法 +fibonacci堆各项步骤的具体分析第3行的INSERT操作： FIB-HEAP-INSERT(H, x) //平摊代价，O（1）. 1 degree[x] ← 0 2 p[x] ← NIL 3 child[x] ← NIL 4 left[x] ← x 5 right[x] ← x 6 mark[x] ← FALSE 7 concatenate the root list containing x with root list H 8 if min[H] = NIL or key[x] < key[min[H]] 9 then min[H] ← x 10 n[H] ← n[H] + 1

第5行的EXTRACT-MIN操作： FIB-HEAP-EXTRACT-MIN(H) //平摊代价为O（lgV） 1 z ← min[H] 2 if z ≠ NIL 3 then for each child x of z 4 do add x to the root list of H 5 p[x] ← NIL 6 remove z from the root list of H 7 if z = right[z] 8 then min[H] ← NIL 9 else min[H] ← right[z] 10 CONSOLIDATE(H) //CONSOLIDATE算法在下面，给出。 11 n[H] ← n[H] - 1 12 return z

下图是FIB-HEAP-EXTRACT-MIN 的过程示意图：

CONSOLIDATE(H) 1 for i ← 0 to D(n[H]) 2 do A[i] ← NIL 3 for each node w in the root list of H 4 do x ← w 5 d ← degree[x] //子女数 6 while A[d] ≠ NIL 7 do y ← A[d]
8 if key[x] > key[y] 9 then exchange x <-> y 10 FIB-HEAP-LINK(H, y, x) //下面给出。 11 A[d] ← NIL 12 d ← d + 1 13 A[d] ← x 14 min[H] ← NIL 15 for i ← 0 to D(n[H]) 16 do if A[i] ≠ NIL 17 then add A[i] to the root list of H 18 if min[H] = NIL or key[A[i]] < key[min[H]] 19 then min[H] ← A[i]

FIB-HEAP-LINK(H, y, x) //y链接至 x。 1 remove y from the root list of H 2 make y a child of x, incrementing degree[x] 3 mark[y] ← FALSE

第8行的RELAX的操作，已上已经给出: RELAX(u, v, w) 1 if d[v] > d[u] + w(u, v) 2 then d[v] ← d[u] + w(u, v) 3 π[v] ← u //O（E）

一般来说，在Dijkstra 算法中，DECREASE-KEY的调用次数远多于EXTRACT-MIN的调用，所以在不增加EXTRACT-MIN 操作的平摊时间前提下，尽量减小DECREASE-KEY操作的平摊时间，都能获得对比二叉堆更快的实现。

以下，是二叉堆，二项堆，斐波那契堆的各项操作的时间复杂度的比较：

操作二叉堆(最坏) 二项堆(最坏) 斐波那契堆(平摊)

MAKE-HEAP Θ(1) Θ(1) Θ(1) INSERT Θ(lg n) O(lg n) Θ(1) MINIMUM Θ(1) O(lg n) Θ(1) EXTRACT-MIN Θ(lg n) Θ(lg n) O(lg n) UNION Θ(n) O(lg n) Θ(1) DECREASE-KEY Θ(lg n) Θ(lg n) Θ(1) DELETE Θ(lg n) Θ(lg n) O(lg n)

Dijkstra 算法+Heap堆完整算法思想在前一篇文章中，我们已经了解到，Dijkstra 算法如下：

DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) //1、初始化结点工作 2 S ← Ø 3 Q ← V[G] //2、初始化队列 4 while Q ≠ Ø 5 do u ← EXTRACT-MIN(Q) //3、从最小队列中，抽取最小结点(在此之前，先建立最小堆) 6 S ← S ∪{u} 7 for each vertex v ∈ Adj[u] 8 do RELAX(u, v, w) //4、松弛操作。

如此，咱们不再赘述，直接即可轻松编写如下c/c++源码：

void dijkstra(ALGraph G,int s,int d[],int pi[],int Q[]) { //Q[]是最小优先队列，Q[1..n]中存放的是图顶点标号,Q[0]中存放堆的大小 //优先队列中有key的概念，这里key可以从d[]中取得。比如说，Q[2]的大小(key)为 d[ Q[2] ]

initSingleSource(G,s,d,pi); //1、初始化结点工作

//2、初始化队列 Q[0] = G.vexnum; for(int i=1;i<=Q[0];i++)

{ Q[i] = i-1; } Q[1] = s; Q[s+1] = 0;

int u; int v; while(Q[0]!=0)

{ buildMinHeap(Q,d); //3.1、建立最小堆 u = extractMin(Q,d); //3.2、从最小队列中，抽取最小结点 ArcNode* arcNodePt = G.vertices[u].firstarc; while(arcNodePt!=NULL) { v = arcNodePt->adjvex; relax(u,v,G,d,pi); //4、松弛操作。 arcNodePt = arcNodePt->nextarc; } }

}

ok，接下来，咱们一步一步编写代码来实现此Dijkstra 算法，先给出第1、初始化结点工作，和4、松弛操作俩个操作的源码：

void initSingleSource(ALGraph G,int s,int d[],int pi[]) { //1、初始化结点工作 for(int i=0;i<G.vexnum;i++)

{ d[i] = INFINITY; pi[i] = NIL; } d[s] = 0; }

void relax(int u,int v,ALGraph G,int d[],int pi[]) { //4、松弛操作。 //u是新加入集合S的顶点的标号 if(d[v]>d[u]+getEdgeWeight(G,u,v))

{ d[v] = d[u] + getEdgeWeight(G,u,v); pi[v] = u; } }

ok，接下来，咱们具体阐述第3个操作，3、从最小队列中，抽取最小结点(在此之前，先建立最小堆)。

Heap最小堆的建立与抽取最小结点在我的这篇文章二、堆排序算法里头，对最大堆的建立有所阐述： 2.3.1、建堆(O（N）)

BUILD-MAX-HEAP(A) 1 heap-size[A] ← length[A] 2 for i ← |length[A]/2| downto 1 3 do MAX-HEAPIFY(A, i)
//建堆，怎么建列?原来就是不断的调用MAX-HEAPIFY(A, i)来建立最大堆。

建最小堆，也是一回事，把上述代码改俩处即可，一，MAX->MIN，二，MAX-HEAPIFY(A, i)->MIN-HEAPIFY(A, i)。如此说来，是不是很简单列，是的，本身就很简单。

先是建立最小堆的工作：

void buildMinHeap(int Q[],int d[]) //建立最小堆 { for(int i=Q[0]/2;i>=1;i--) { minHeapify(Q,d,i); //调用minHeapify，以保持堆的性质。 } }

然后，得编写minHeapify代码，来保持最小堆的性质：

void minHeapify(int Q[],int d[],int i) { //smallest,l,r,i都是优先队列元素的下标，范围是从1 ~ heap-size[Q] int l = 2i; int r = 2i+1; int smallest; if(l<=Q[0] && d[ Q[l] ] < d[ Q[i] ])

{ smallest = l; } else { smallest = i; } if(r<=Q[0] && d[ Q[r] ] < d[ Q[smallest] ])

{ smallest = r; } if(smallest!=i) { int temp = Q[i]; Q[i] = Q[smallest]; Q[smallest] = temp;

minHeapify(Q,d,smallest); } }

你自个比较一下建立最小堆，与建立最大堆的代码，立马看见，如出一辙，不过是改几个字母而已：

MAX-HEAPIFY(A, i) //建立最大堆的代码 1 l ← LEFT(i) 2 r ← RIGHT(i) 3 if l ≤ heap-size[A] and A[l] > A[i] 4 then largest ← l 5 else largest ← i 6 if r ≤ heap-size[A] and A[r] > A[largest] 7 then largest ← r 8 if largest ≠ i 9 then exchange A[i] <-> A[largest] 10 MAX-HEAPIFY(A, largest)

ok，最后，便是3、从最小队列中，抽取最小结点的工作了，如下：

int extractMin(int Q[],int d[]) //3、从最小队列中，抽取最小结点 { //摘取优先队列中最小元素的内容，这里返回图中顶点的标号(0 ~ G.vexnum-1)， //这些标号是保存在Q[1..n]中的 if(Q[0]<1) { cout<<"heap underflow!"<<endl; return -10000; } int min = Q[1]; Q[1] = Q[Q[0]]; Q[0] = Q[0] - 1; minHeapify(Q,d,1); return min; }

ALGraph图的建立先定义几个宏，

#define MAX_VERTEX_NUM 20 //图中最大的节点数目 #define INFINITY 10000 #define NIL -1

再建立几个数据结构：

typedef struct ArcNode //弧节点，就是邻接链表的表节点 {
int adjvex; //该弧所指向尾节点的位置，其实保存的就是数组的下标 ArcNode *nextarc; //指向下一条弧的指针 int weight; //权重。 }ArcNode;

typedef struct VNode { ArcNode* firstarc; }VNode,AdjList[MAX_VERTEX_NUM];

typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph;

编写几个功能函数：

void initALGraph(ALGraph* GPt,int vn) //初始化结点 { GPt->arcnum = 0; GPt->vexnum = vn; for(int i=0;i<vn;i++)

{ GPt->vertices[i].firstarc = NULL; } }

void insertArc(ALGraph* GPt,int vhead,int vtail,int w) //增加结点操作 { ArcNode* arcNodePt = new ArcNode; arcNodePt->nextarc = NULL; arcNodePt->adjvex = vtail; arcNodePt->weight = w;

ArcNode* tailPt = GPt->vertices[vhead].firstarc; if(tailPt==NULL) { GPt->vertices[vhead].firstarc = arcNodePt; } else { while(tailPt->nextarc!=NULL) { tailPt = tailPt->nextarc; } tailPt->nextarc = arcNodePt; } GPt->arcnum ++; }

void displayGraph(ALGraph G) //打印结点 { ArcNode* arcNodePt; for(int i=0;i<G.vexnum;i++) { arcNodePt = G.vertices[i].firstarc; cout<<"vertex"<<i<<": "; while(arcNodePt!=NULL) { cout<adjvex<<"("<<"weight"<weight<<")"<<" "; arcNodePt = arcNodePt->nextarc; } cout<<endl; } }

int getEdgeWeight(ALGraph G,int vhead,int vtail) //求边的权重 { ArcNode* arcNodePt = G.vertices[vhead].firstarc; while(arcNodePt!=NULL) { if(arcNodePt->adjvex==vtail) { return arcNodePt->weight; } arcNodePt = arcNodePt->nextarc; } return INFINITY; }

fibonacci堆实现Dijkstra 算法

ok，闲话少说，咱们切入正题。下面，咱们来一步一步利用fibonacci堆实现Dijkstra 算法吧。

前面说了，要实现一个算法，首先得明确其算法原理及思想，而要理解一个算法的原理，又得知道发明此算法的目的是什么，即，此算法是用来干什么的?

由前面的例子，我们可以总结出：Dijkstra 算法是为了解决一个点到其它点最短距离的问题。

我们总是要找源点到各个目标点的最短距离，在寻路过程中，如果新发现了一个新的点，发现当源点到达前一个目的点路径通过新发现的点时，路径可以缩短，那么我们就必须及时更新此最短距离。

ok，举个例子：如我们最初找到一条路径，A->B，这条路径的最短距离为6，后来找到了C点，发现若A->C->B点路径时，A->B的最短距离为5，小于之前找到的最短距离6，所以，便得此更新A到B的最短距离：为5，最短路径为A->C->B.

好的，明白了此算法是干什么的，那么咱们先用伪代码尝试写一下吧(有的人可能会说，不是吧，我现在，什么都还没搞懂，就要我写代码了。额，你手头不是有资料么，如果全部所有的工作，都要自己来做的话，那就是一个浩大的工程了。:D。)。

咱们先从算法导论上，找来Dijkstra 算法的伪代码如下：

DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) //1、初始化结点工作 2 S ← Ø 3 Q ← V[G] //2、插入结点操作 4 while Q ≠ Ø 5 do u ← EXTRACT-MIN(Q) //3、从最小队列中，抽取最小点工作 6 S ← S ∪{u} 7 for each vertex v ∈ Adj[u] 8 do RELAX(u, v, w) //4、松弛操作。

伪代码毕竟与能在机子上编译运行的代码，还有很多工作要做。

首先，咱们看一下上述伪代码，可以看出，基本上，此Dijkstra 算法主要分为以下四个步骤：

1、初始化结点工作 2、插入结点操作 3、从最小队列中，抽取最小点工作 4、松弛操作。

ok，由于第2个操作涉及到斐波那契堆，比较复杂一点，咱们先来具体分析第1、2、4个操作：

1、得用O（V）的时间，来对最短路径的估计，和对前驱进行初始化工作。

INITIALIZE-SINGLE-SOURCE(G, s) 1 for each vertex v ∈ V[G] 2 do d[v] ← ∞ 3 π[v] ← NIL //O（V） 4 d[s] 0

我们根据上述伪代码，不难写出以下的代码：

void init_single_source(Graph *G,int s) { for (int i=0;in;i++) { d[i]=INF; pre[i]=-1; } d[s]=0; }

2、插入结点到队列的操作

2 S ← Ø 3 Q ← V[G] //2、插入结点操作

代码： for (i=0;in;i++) S[i]=0;

4、松弛操作。首先得理解什么是松弛操作： Dijkstra 算法使用了松弛技术，对每个顶点v<-V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径的估计。 RELAX(u, v, w) 1 if d[v] > d[u] + w(u, v) 2 then d[v] ← d[u] + w(u, v) 3 π[v] ← u //O（E）

同样，我们不难写出下述代码： void relax(int u,int v,Graph *G) { if (d[v]>d[u]+G->w[u][v]) { d[v] = d[u]+G->w[u][v]; //更新此最短距离 pre[v]=u; //u为v的父结点 } }

再解释一下上述relax的代码，其中u为v的父母结点，当发现其父结点d[u]加上经过路径的距离G->w[u][v]，小于子结点到源点的距离d[v]，便得更新此最短距离。
请注意，说的明白点：就是本来最初A到B的路径为A->B，现在发现，当A经过C到达B时，此路径距离比A->B更短，当然，便得更新此A到B的最短路径了，即是：A->C->B，C 即成为了B的父结点(如此解释，我相信您已经明朗。:D。)。
即A=>B <== A->C->B，执行赋值操作。

ok，第1、2、4个操作步骤，咱们都已经写代码实现了，那么，接下来，咱们来编写第3个操作的代码：3、从最小队列中，抽取最小点工作。

相信，你已经看出来了，我们需要构造一个最小优先队列，那用什么来构造最小优先队列列?对了，堆。什么堆最好，效率最高，呵呵，就是本文要实现的fibonacci堆。

为什么?ok，请看最小优先队列的三种实现方法比较：

     EXTRACT-MIN + RELAX

I、简单方式： O（VV + E1） II、二叉/项堆： O（VlgV + |E|lgV）源点可达：O（ElgV）稀疏图时，有E=o（V^2/lgV）， => O（V^2）
III、斐波那契堆：O（VlgV + E）

其中，V为顶点，E为边。好的，这样我们就知道了：Dijkstra 算法中，当用斐波纳契堆作优先队列时，算法时间复杂度为O（V*lgV + E）。

额，那么接下来，咱们要做的是什么列?当然是要实现一个fibonacci堆了。可要怎么实现它，才能用到我们

Dijkstra 算法中列?对了，写成一个库的形式。库?呵呵，是一个类。

    ok，以下就是这个fibonacci堆的实现：

//FibonacciHeap.h
#ifndef FIBONACCI_HEAP_H_INCLUDED
#define FIBONACCI_HEAP_H_INCLUDED

#include
#include

template
struct Fib_node
{
Fib_node* ns_; //后驱结点
Fib_node pt_; //父母结点
Fib_node ps_; //前驱结点
Fib_node* fc_; //头结点
int rank_; //孩子结点
bool marked_; //孩子结点是否删除的标记
T* pv_;
Fib_node(T* pv = 0) : pv_(pv) { }
T& value(void) { return pv_; }
void set_src(T pv) { pv_ = pv; }
}; //Fib_node的数据结构

template<class Node, class OD>
Node* merge_tree(Nodea, Node b, OD small) //合并结点
{
if(small(b->value(), a->value()))
swap(a, b);
Node* fc = a->fc_;
a->fc_ = b;
a->ns_ = a->ps_ = a->pt_ = 0;
++a->rank_;

b->pt_ = a; //a为b的父母
b->ns_ = fc; //第一个结点赋给b的前驱结点
b->ps_ = 0;
if(fc != 0)
fc->ps_ = b;
return a;
}

template
void erase_node(Node* me) //删除结点
{
Node* const p = me->pt_;
--p->rank_;
if(p->fc_ == me) //如果me是头结点
{
if((p->fc_ = me->ns_) != 0)
me->ns_->ps_ = 0;
}
else
{
Node *prev = me->ps_;
Node *next = me->ns_; //可能为0
prev->ns_ = next;
if(next != 0)
next->ps_ = prev;
}
}

template<class Node, class OD>
Node* merge_fib_heap(Node* a, Node* b, OD small) //调用上述的merge_tree合并fib_heap。
{
enum {SIZE = 64}; //
Node* v[SIZE] = {0};
int k;
while(a != 0)
{
Node* carry = a;
a = a->ns_;
for(k = carry->rank_; v[k] != 0; ++k)
{
carry = merge_tree(carry, v[k], small);
v[k] = 0;
}
v[k] = carry;
}
while(b != 0)
{
Node* carry = b;
b = b->ns_;
for(k = carry->rank_; v[k] != 0; ++k)
{
carry = merge_tree(carry, v[k], small);
v[k] = 0;
}
v[k] = carry;
}
Node** t = std::remove(v, v+SIZE, (Node*)0);
int const n = t - v;
if(n > 0)
{
for(k = 0; k < n - 1; ++k)
v[k]->ns_ = v[k+1];
for(k = 1; k < n; ++k)
v[k]->ps_ = v[k-1];
v[n-1]->ns_ = v[0]->ps_ = 0;
}
return v[0];
}

template<typename T, class OD = std::less >
struct Min_fib_heap //抽取最小结点
{
typedef Fib_node Node;
typedef Node Node_type;

Node* roots_;
Node* min_; //pointer to the minimum node
OD less_;

Min_fib_heap(void): roots_(0), min_(0), less_() { }
bool empty(void) const { return roots_ == 0; }
T& top(void) const { return min_->value(); }

void decrease_key(Node* me) //删除
{ //precondition: root_ not zero
if(less_(me->value(), min_->value()))
min_ = me;
cascading_cut(me);
}
void push(Node* me) //压入
{
me->pt_ = me->fc_ = 0;
me->rank_ = 0;
if(roots_ == 0)
{
me->ns_ = me->ps_ = 0;
me->marked_ = false;
roots_ = min_ = me;
}
else
{
if(less_(me->value(), min_->value()))
min_ = me;
insert2roots(me);
}
}
Node* pop(void) //弹出
{
Node* const om = min_;
erase_tree(min_);
min_ = roots_ = merge_fib_heap(roots_, min_->fc_, less_);
if(roots_ != 0) //find new min_
{
for(Node* t = roots_->ns_; t != 0; t = t->ns_)
if(less_(t->value(), min_->value()))
min_ = t;
}
return om;
}
void merge(void) //合并
{
if(empty()) return;
min_ = roots_ = merge_fib_heap(roots_, (Node*)0, less_);
for(Node* a = roots_->ns_; a != 0; a = a->ns_)
if(less_(a->value(), min_->value() ))
min_ = a;
}
private:
void insert2roots(Node* me) //插入
{ //precondition: 1) root_ != 0; 2) me->value() >= min_->value()
me->pt_ = me->ps_ = 0;
me->ns_ = roots_;
me->marked_ = false;
roots_->ps_ = me;
roots_ = me;
}
void cascading_cut(Node* me) //断开
{ //precondition: me is not a root. that is me->pt_ != 0
for(Node* p = me->pt_; p != 0; me = p, p = p->pt_)
{
erase_node(me);
insert2roots(me);
if(p->marked_ == false)
{
p->marked_ = true;
break;
}
}
}
void erase_tree(Node* me) //删除
{
if(roots_ == me)
{
roots_ = me->ns_;
if(roots_ != 0)
roots_->ps_ = 0;
}
else
{
Node* const prev = me->ps_;
Node* const next = me->ns_;
prev->ns_ = next;
if(next != 0)
next->ps_ = prev;
}
}
}; //Min_fib_heap的类

template
bool is_sorted(Fitr first, Fitr last)
{
if(first != last)
for(Fitr prev = first++; first != last; prev = first++)
if(*first < *prev) return false;
return true;
}
template<typename Fitr, class OD>
bool is_sorted(Fitr first, Fitr last, OD cmp)
{
if(first != last)
for(Fitr prev = first++; first != last; prev = first++)
if(cmp(*first, *prev)) return false;
return true;
}

    由于本BLOG日后会具体阐述这个斐波那契堆的各项操作，限于篇幅，在此，就不再啰嗦解释上述程序了。

    ok，实现了fibonacci堆，接下来，咱们可以写Dijkstra 算法的代码了。为了版述清晰，再一次贴一下此算法的伪代码：

DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) 2 S ← Ø 3 Q ← V[G] //第3行，INSERT操作，O（1） 4 while Q ≠ Ø 5 do u ← EXTRACT-MIN(Q) //第5行，EXTRACT-MIN操作，VlgV 6 S ← S ∪{u} 7 for each vertex v ∈ Adj[u] 8 do RELAX(u, v, w) //第8行，RELAX操作，EO(1)

 编写的Dijkstra算法的c代码如下：

void Dijkstra(int s, T d[], int p[])
{
//寻找从顶点s出发的最短路径,在d中存储的是s->i的最短距离
//p中存储的是i的父节点
if (s < 1 || s > n)
throw OutOfBounds();

//路径可到达的顶点列表,这里可以用上述实现的fibonacci堆代码。   
Chain<int> L;      

ChainIterator<int> I;     
//初始化d, p, and L     
for (int i = 1; i <= n; i++)     
{     
    d[i] = a[s][i];     
     
    if (d[i] == NoEdge)      
    {     
        p[i] = 0;     
    }     
    else      
    {     
        p[i] = s;      
        L.Insert(0,i);     
    }     
}     

//更新d, p     
while (!L.IsEmpty())      
{     
    //寻找最小d的点v     
    int *v = I.Initialize(L);     
    int *w = I.Next();     
    while (w)     
    {     
        if (d[*w] < d[*v])     
            v = w;     

        w = I.Next();     
    }     

    int i = *v;     
    L.Delete(*v);     
    for (int j = 1; j <= n; j++)      
    {     
        if (a[i][j] != NoEdge      
            && (!p[j] || d[j] > d[i] + a[i][j]))    //d[i]是父节点  
        {     
            // 刷新更小的d[j]      
            d[j] = d[i] + a[i][j];     

            // 如果j没有父节点,则添加到L     
            if (!p[j])      
                L.Insert(0,j);     

            // 更新父节点     
            p[j] = i;     
        }     
    }     
}

}

更好的代码，还在进一步修正中。日后，等完善好后，再发布整个工程出来。

dijkstra算法实现 - decoqt/mywiki GitHub Wiki

Dijkstra 算法

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️