作者:JULY、二零一一年三月十八日
出處：http://blog.csdn.net/v_JULY_v。
------------------------------------------
引言：
此文的寫作目的很簡單，就一個理由，個人認為：上一篇文章，二之再續、Dijkstra 算法 fibonacci堆的逐步c實現，寫的不夠好，特此再寫Dijkstra 算法的一個續集，謂之二之三續。
鑒於讀者理解斐波那契堆的難度，本文，以簡單的最小堆為示例。同時，本程序也有參考網友的實現。有任何問題，歡迎指正。
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 = 2*i;
int r = 2*i+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<<arcNodePt->adjvex<<"("<<"weight"<<arcNodePt->weight<<")"<<" ";
arcNode
