數據結構應用詳解-

概述

最小生成樹——無向連通圖的所有生成樹中有一棵邊的權值總和最小的生成樹

拓撲排序 ——由偏序定義得到拓撲有序的操作便是拓撲排序。建立模型是AOV網

關鍵路徑——在AOE-網中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度，路徑長度最長的路徑叫做關鍵路徑(Critical Path)。

最短路徑——最短路徑問題是圖研究中的一個經典算法問題， 旨在尋找圖（由結點和路徑組成的）中兩結點之間的最短路徑。

1.最小生成樹

1.1 問題背景：
    假設要在n個城市之間建立通信聯絡網，則連通n個城市只需要n—1條線路。這時，自然會考慮這樣一個問題，如何在最節省經費的前提下建立這個通信網。在每兩個城市之間都可以設置一條線路，相應地都要付出一定的經濟代價。n個城市之間，最多可能設置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的耗費最少呢?
1.2 分析問題（建立模型）：

可以用連通網來表示n個城市以及n個城市間可能設置的通信線路，其中網的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權值表示相應的代價。對于n個頂點的連通網可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網。即無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經過的邊的集合及圖中所有頂點的集合就構成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得到不同的生成樹。

圖 G5無向連通圖的生成樹 為(a)、(b)和(c)圖所示：

                                     G5

   G5的三棵生成樹：

可以證明，對于有n 個頂點的無向連通圖，無論其生成樹的形態如何，所有生成樹中都有且僅有n－1 條邊。

1.3最小生成樹的定義：

如果無向連通圖是一個網，那么，它的所有生成樹中必有一棵邊的權值總和最小的生成樹，我們稱這棵生成樹為最小生成樹，簡稱為最小生成樹。

最小生成樹的性質：
假設N=(V,{ E}) 是個連通網，U是頂點集合V的一個非空子集，若（u,v）是個一條具有最小權值(代價)的邊，其中，

則必存在一棵包含邊（u,v）的最小生成樹。

1.4 解決方案：

兩種常用的構造最小生成樹的算法：普里姆（Prim）和克魯斯卡爾（Kruskal）。他們都利用了最小生成樹的性質

1.普里姆（Prim）算法：有線到點，適合邊稠密。時間復雜度O(N^2)

假設G＝（V，E）為連通圖，其中V 為網圖中所有頂點的集合，E 為網圖中所有帶權邊的集合。設置兩個新的集合U 和T，其中

集合U（頂點集） 用于存放G 的最小生成樹中的頂點，

     集合T  （邊集合）存放G 的最小生成樹中的邊。

     T ，U的初始狀態：令集合U 的初值為U＝{u1}（假設構造最小生成樹時，從頂點u1 出發），集合T 的初值為T＝{}。

     Prim 算法的思想是：從所有u∈U，v∈V－U 的邊中，選取具有最小權值的邊（u，v）∈E，將頂點v 加入集合U 中，將邊（u，v）加入集合T 中，如此不斷重復，直到U＝V 時，最小生成樹構造完畢，這時集合T 中包含了最小生成樹的所有邊。

Prim 算法可用下述過程描述，其中用wuv 表示頂點u 與頂點v 邊上的權值。
（1）U＝{u1},T={};
（2）while (U≠V)do
           (u，v)＝min{wuv；u∈U，v∈V－U }
          T＝T＋{(u，v)}
          U＝U＋{v}
（3）結束。
按照Prim 方法，從頂點1 出發，該網的最小生成樹的產生過程如圖

為實現Prim 算法，需設置兩個輔助closedge，用來保存U到集合V－U 的各個頂點中具有最小權值的邊的權值。對每個Vi∈（V-U ）在輔助數組中存在一個相應的分量closedge[i-1],它包括兩個域：

typedef struct ArcNode   
{  
    int adjvex;          //adjex域存儲該邊依附的在U中的頂點
    VrType lowcost;      //lowcost域存儲該邊上的權重
}closedge[MAX_VERTEX_NUM];

顯然：

初始狀態時，U＝{v1}(u1 為出發的頂點),則到V-U 中各項中最小的邊，即依附頂點v1的各條邊中，找到一條代價最小的邊（u0，v0）= （1，3）為生成樹上一條邊。

同時將v0（=v3）并入集合U中。然后修改輔助數組的值。

1）將closedge[2].lowcost = 0；//表示頂點V3三已經并入U

2) 由于邊（v2,v3）的權值小于closedge[1].lowcost，故需修改closedge[1]為邊（v2,v3）及其權值，同理修改closedge[4]，closedge[5].

   closedge[1].adjvex  = 3.

   closedge[1].lowcost = 5.

   closedge[4].adjvex  = 1.

   closedge[4].lowcost = 5.

    closedge[5].adjvex  = 3.

   closedge[5].lowcost = 6.

以此類推，直至U = V;

下圖 給出了在用上述算法構造網圖7.16的最小生成樹的過程中：

 
Prim 算法實現：

按照算法框架:

（1）U＝{u1},T={};
（2）while (U≠V)do
           (u，v)＝min{wuv；u∈U，v∈V－U }
          T＝T＋{(u，v)}
          U＝U＋{v}
（3）結束。

當無向網采用二維數組存儲的鄰接矩陣存儲時，Prim 算法的C 語言實現為：

//記錄從頂點集U到V—U的代價最小的邊的輔助數組定義：  
    // struct{  
    // VertexType adjvex；  
    // VRType lowcost；  
    // }closedge[ MAX_VERTEX_NUM ]   
void MiniSpanTree_PRIM (MGraph G，VertexType u){  
//用普里姆算法從第u個頂點出發構造網G的最小生成樹T，輸出T的各條邊。  
    k =LocateVex(G，u)；   
    for(j=0； j<G.vexnum； ++j)  
        if(j!=k) closedge[j] ={u ,G.arcs[k][j].adj}; // {adjvex , lowcost}   
    closedge[k].lowcost =0； //初始，U={u}  
    for( i=1；i<G.vexnum；++i){ //選擇其余G.vexnum-1個頂點  
        k=minimum(closedge)；  
        printf(closedge[k].adjvex, G.vexs[k]);//輸出生成樹的邊  
        //第k頂點并入U集  
        closedge[k].lowcost=0;  
        for(j=0; j<G.vexnum; ++j)  
            if (G.acrs[k][j].adj<closedge[j].lowcost) closedge[j]={G.vexs[k],G.arcs[k][j].adj};  
    }//for  
}//MiniSpanTree

2.克魯斯卡爾（Kruskal） :由點到線，適合邊稀疏的網。時間復雜度：O(e * loge)

Kruskal 算法是一種按照網中邊的權值遞增的順序構造最小生成樹的方法。

基本思想是：

1) 設無向連通網為G＝（V，E），令G 的最小生成樹為T，其初態為T＝（V，{}），即開始時，最小生成樹T 由圖G 中的n 個頂點構成，頂點之間沒有一條邊，這樣T 中各頂點各自構成一個連通分量。

2) 在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量，則將此邊加入到T中，否則舍棄此邊而選擇下一條邊（若該邊依附的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路）。依此類推，當T 中的連通分量個數為1 時，此連通分量便為G 的一棵最小生成樹。

按照Kruskal 方法構造最小生成樹的過程如圖所示：

在構造過程中，按照網中邊的權值由小到大的順序，不斷選取當前未被選取的邊集中權值最小的邊。依據生成樹的概念，n 個結點的生成樹，有n－1 條邊，故反復上述過程，直到選取了n－1 條邊為止，就構成了一棵最小生成樹。

Kruskal 算法的實現：
算法的框架：

構造非連通圖T＝（V，{}）

k = i= 0；//k為邊數

while（k《< n-1） {

     i++;

    檢查邊E中第i條邊的權值

    最小邊（u，v）

    若（u，v） 加入T不是T產生回路，

    則（u，v）加入T，且k++

}

 c語言實現：

C 語言實現Kruskal 算法，其中函數Find 的作用是尋找圖中頂點所在樹的根結點在數組father 中的序號。需說明的是，在程序中將頂點的數據類型定義成整型，而在實際應用中，可依據實際需要來設定。

typedef int elemtype;  
typedef struct {  
elemtype v1;  
elemtype v2;  
int cost;  
}EdgeType;  
void Kruskal（EdgeType edges[ ]，int n）  
/*用Kruskal 方法構造有n 個頂點的圖edges 的最小生成樹*/  
{ int father[MAXEDGE];  
int i,j,vf1,vf2;  
for (i=0;i<n;i++) father[i]=-1;  
i=0;j=0;  
while(i<MAXEDGE && j<n-1)  
{ vf1=Find(father,edges[i].v1);  
vf2=Find(father,edges[i].v2);  
if (vf1!=vf2)  
{ father[vf2]=vf1;  
j++;  
printf(“%3d%3d\n”,edges[i].v1,edges[i].v2);  
}  
i++;  
}  
}  
  
//find 函數  
int Find（int father[ ]，int v）  
/*尋找頂點v 所在樹的根結點*/  
{ int t;  
t=v;  
while(father[t]>=0)  
t=father[t];  
return(t);  
}

2. AOV網與拓撲排序

2. 1．AOV網(Activity on vertex network)     

      所有的工程或者某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為活動。若以圖中的頂點來表示活動，有向邊（?。┍硎净顒又g的優先關系，則這樣活動在頂點上的有向圖稱為AOV 網（Activity On Vertex Network）。在AOV 網中，若從頂點i到頂點j之間存在一條有向路徑，稱頂點i是頂點j的前驅，或者稱頂點j 是頂點i的后繼。若<i,j>是圖中的弧，則稱頂點i是頂點j 的直接前驅，頂點j 是頂點i 的直接后驅。

      AOV 網中的弧表示了活動之間存在的制約關系。例如，計算機專業的學生必須完成一系列規定的基礎課和專業課才能畢業。學生按照怎樣的順序來學習這些課程呢？這個問題可以被看成是一個大的工程，其活動就是學習每一門課程。這些課程的名稱與相應代號如表所示。

課程之間的優先關系圖：

該圖的拓撲有序系列：

注意：
    在AOV-網中不應該出現有向環，因為存在環意味著某項活動應以自己為先決條件。若設計出這樣的流程圖，工程便無法進行。而對程序的數據流圖來說，則表明存在一個死循環。因此，對給定的AOV-網應首先判定網中是否存在環。檢測的辦法是對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV-網中必定不存在環。

2.2．拓撲排序 

離散數學基礎知識：

首先復習一下離散數學中的偏序集合與全序集合兩個概念。

若集合A 中的二元關系R 是自反的、非對稱的和傳遞的，則R 是A 上的偏序關系。集合A 與關系R 一起稱為一個偏序集合。

若R 是集合A 上的一個偏序關系，如果對每個a、b∈A 必有aRb 或bRa ，則R 是A上的全序關系。集合A 與關系R 一起稱為一個全序集合。

直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。

[例如]，圖7.25所示的兩個有向圖，圖中弧(x,y)表示x≤y，則(a)表示偏序，(b)表示全序。若在(a)的有向圖上人為地加一個表示v2≤v3的弧(符號“≤”表示v2領先于v3)，則(a)表示的亦為全序，且這個全序稱為拓撲有序(Topological Order)，而由偏序定義得到拓撲有序的操作便是拓撲排序。

3.3  拓撲排序算法

對AOV 網進行拓撲排序的方法和步驟是：
1、從AOV 網中選擇一個沒有前驅的頂點（該頂點的入度為0）并且輸出它；
2、從網中刪去該頂點，并且刪去從該頂點發出的全部有向邊；
3、重復上述兩步，直到剩余的網中不再存在沒有前驅的頂點為止。

這樣操作的結果有兩種：一種是網中全部頂點都被輸出，這說明網中不存在有向回路；另一種就是網中頂點未被全部輸出，剩余的頂點均不前驅頂點，這說明網中存在有向回路。

以下圖(a)中的有向圖為例，圖中v1，和v6沒有前驅，則可任選一個。假設先輸出v6, 在刪除v6及弧<v6，v4>，<v6，v5>之后，只有頂點v1沒有前驅，則輸出vl且刪去vl及弧<v1，v2>、<v1，v3>和<v1, v4>，之后v3和v4都沒有前驅。依次類推，可從中任選一個繼續進行。最后得到該有向圖的拓撲有序序列為：

 v6 – v1 – v4 – v3 – v2 – v5

            圖AOV-網及其拓撲有序序列產生的過程
(a)AOV-網；(b)輸出v6之后；(c)輸出v1之后；(d)輸出v4之后；(e)輸出v3之后；(f)輸出v2之后 

為了實現上述算法，對AOV 網采用鄰接表存儲方式，并且鄰接表中頂點結點中增加一個記錄頂點入度的數據域，即頂點結構設為：

頂點表結點結構的描述改為：

typedef struct vnode{ /*頂點表結點*/
int count /*存放頂點入度*/
VertexType vertex; /*頂點域*/
EdgeNode * firstedge; /*邊表頭指針*/
}VertexNode;

當然也可以不增設入度域，而另外設一個一維數組來存放每一個結點的入度。算法中可設置了一個堆棧，凡是網中入度為0 的頂點都將其入棧。為此，拓撲排序的算法步驟為：
1、將沒有前驅的頂點（count 域為0）壓入棧；
2、從棧中退出棧頂元素輸出，并把該頂點引出的所有有向邊刪去，即把它的各個鄰接頂點的入度減1；
3、將新的入度為0 的頂點再入堆棧；
4、重復②～④，直到棧為空為止。此時或者是已經輸出全部頂點，或者剩下的頂點中沒有入度為0 的頂點。

為了避免重復檢測入度為零的頂點，可另設一棧暫存所有入度為零的頂點。

Status Topological Sort(ALGraph G){  
//有向圖G采用鄰接表存儲結構。  
//若G無回路，則輸出G的頂點的1個拓撲序列并返回OK，否則ERROR。  
    FindInDegree(G，indegree)； //對各頂點求入度indegree[0..vernum-1]  
    InitStack(S)；  
    for(i=0；i<G.vexnum； ++i)  
    if(!indegree[i])Push(S，i) //建零入度頂點棧,s入度為0者進棧  
    count=0； //對輸出頂點計數   
    while (!StackEmpty(S)) {  
        Pop(S，i)；   
        printf(i，G.vertices[i].data)； ++count； //輸出i號頂點并計數   
        for(p=G.vertices[i].firstarc；p； p=p—>nextarc) {  
            k=p—>adivex； //對i號頂點的每個鄰接點的入度減1  
            if(！(--indegree[k]))Push(S，k)；//若入度減為0，則入棧  
        }//for  
    }//while  
    if(count<G.vexnum) return ERROR； //該有向圖有回路  
    else return OK；  
}//TopologicalSort

3. 關鍵路徑(AOE網)

3.1AOE網：（Activity on edge network）
      AOE網示意圖若在帶權的有向圖中，以頂點表示事件，以有向邊表示活動，邊上的權值表示活動的開銷（如該活動持續的時間），則此帶權的有向圖稱為AOE網。

3.2 實際問題：

      如果用AOE網來表示一項工程，那么，僅僅考慮各個子工程之間的優先關系還不夠，更多的是關心整個工程完成的最短時間是多少；哪些活動的延期將會影響整個工程的進度，而加速這些活動是否會提高整個工程的效率。因此，通常在AOE網中列出完成預定工程計劃所需要進行的活動，每個活動計劃完成的時間，要發生哪些事件以及這些事件與活動之間的關系，從而可以確定該項工程是否可行，估算工程完成的時間以及確定哪些活動是影響工程進度的關鍵。

如圖是一個假想的有11項活動的AOE-網：

其中有9個事件v1，v2，v3，…，v9，每個事件表示在它之前的活動已經完成，在它之后的活動可以開始。如v1表示整個工程開始，v9表示整個工程結束，v5表示a4和a5已經完成，a7和a8可以開始。與每個活動相聯系的數是執行該活動所需的時間。比如，活動a1需要6天，a2需要4天等。

 和AOV-網不同，對AOE-網有待研究的問題是：
    (1)完成整項工程至少需要多少時間?
    (2)哪些活動是影響工程進度的關鍵?
3.3 關鍵路徑

由于在AOE-網中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(這里所說的路徑長度是指路徑上各活動持續時間之和，不是路徑上弧的數目)。路徑長度最長的路徑叫做關鍵路徑(Critical Path)。

AOE網有關的概念：
1)路徑長度：路徑上各個活動的持續時間之和

2)完成工程的最短時間：由于AOE網中有活動是并行進行的，所以完成工程的最短時間就是從開始點到完成點的最長路勁長度。
3)活動最早開始時間(earlist time)(e(i))：從開始點到頂點vi的最長路徑稱為事件vi的最早發生時間。這個時間決定了以vi為尾的弧表示的活動的最早開始時間.

4)活動最晚開始時間(latest time)(l(i))：在不推遲整個工程完成的前提下，活動最遲開始的時間
5)完成活動的時間余量：該活動的最遲開始時間減去最早開始時間
6)關鍵路徑(critical path)：路徑長度最長的路徑稱為關鍵路徑
7)關鍵活動(critical activity):關鍵路徑上的活動稱為關鍵活動，關鍵活動的特點是:e(i)=l(i)分析關鍵路徑的目的就是辨別在整個工程中哪些是關鍵活動，以便爭取提高關鍵活動的工作效率，縮短整個工程的工期。

3.4  解決方案：
    由上分析可知，辨別關鍵活動就是要找e(i)=l(i)的活動。為了求得AOE-網中活動的e(i)和l(i)， 首先求事件的最早發生時間ve(j)和最遲發生時間vl(j)。如果活動ai由弧<j,k>表示，其持續時間記為dut(<j,k>),則有如下關系：

      e(i ) = ve(j)              

     l(i) = vl(k)-dut(<j,k>)

    求ve(j)和vl(j)需分兩步進行：
    （1）從ve(0)開始向前遞推
         
        其中，T是所有以第j個頂點為頭的弧的結合。
    （2）從vl(n-1)=ve(n-1)起向后遞推
                

其中，S是所有以第i個頂點為尾的弧的集合。 
    這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。也就是說ve(j-1)必須在vj的所有前驅的最早發生時間求得之后才能確定，而vl(j-1)則必須在vj的所有后繼的最遲發生時間求得之后才能確定。因此，可以在拓撲排序的基礎上計算ve(j-1)和vl(j-1)。

3.5 關鍵路徑的算法：
    (1)輸入e條弧<j，k>，建立AOE-網的存儲結構； 
    (2)從源點v0出發，令ve[0]=0，按拓撲有序求其余各頂點的最早發生時間ve[i] (1≤i≤n-1)。如果得到的拓撲有序序列中頂點個數小于網中頂點數n，則說明網中存在環，不能求關鍵路徑，算法終止；否則執行步驟(3)。
    (3)從匯點vn出發，令vl[n-1]=ve[n-1]，按逆拓撲有序求其余各頂點的最遲發生時間vl[i](n-2≥i≥0)；
    (4)根據各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間 l(s)。若某條弧滿足條件e(s)=l(s)，則為關鍵活動。 
 先將拓撲排序算法：TopologicalOrder（）

CriticalPath便為求關鍵路徑的算法：

Status TopologicalOrder(ALGraph G，Stack &T){  
//有向網G采用鄰接表存儲結構，求各頂點事件的最早發生時間ve(全局變量)。  
//T為拓撲序列頂點棧，s為零入度頂點棧。若G無回路，返回G的一拓撲序列，函數值為OK，否則ERROR。   
    FindInDegree(G，indegree)；//對各頂點求入度indegree[0..vernum-1]  
    for(i=0；i<G.vexnum； ++i)     
    if(!indegree[i])Push(S，i) //建零入度頂點棧,s入度為0者進棧   
    InitStack(T)； count=0；ve[0..G.vexnum-1]=0； //初始化   
    while(!StackEmpty(S)){ //j號頂點入T棧并計數  
        Pop(S，j)； Push(T，j)；++count;  
        for(p=G.vertices[j].firstarc；p；p=p->nextarc){  
            k=p—>adjvex； //對i號頂點的每個鄰接點的入度減l  
            if(--indegree[k]==0)Push(S，k)； //若入度減為0，則入棧  
            if(ve[j]+*(p->info)>ve[k] ) ve[k]=ve[j]+*(p->info)；    
  
         }//for *(p->info)=dut(<j,k>)   
  
    }//while   
    if(count<G.vexnum) return ERROR； //該有向網有回路  
    else return OK；  
  
}//TopologicalOrder   
  
  
  
  
Status CriticalPath (ALGraph G){ //G為有向網，輸出G的各項關鍵活動。  
    if(!TopologicalOrder(G，T)) return ERROR；    //初始化頂點事件的最遲發生時間   
    vl[0..G.vexnum-1]=ve[0..C.vexnum-1]； //按拓撲逆序求各頂點的vl值  
    while(!StackEmpty(T))  
        for( Pop(T, j), p=G.vertices[j].firstarc；p； p=p->nextarc){  
            k=p->adjvex； dut=*(p—>info)； //dut<i，k>  
            if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut；  }//for  
    for(j=0；j<G.vexnum；++j) //求ee，el和關鍵活動  
        for(p=G.vertices[j]；p；p=p->nextarc){  
            k=p->adjvex； dut=*(p—>info)；ee=ve[j]；el=v1[k]-dut；tag = (ee==e1) ? ‘*’ ： ‘’；  
            printf(j，k，dut，ee，el，tag)； //輸出關鍵活動    
}   
}//CriticalPath

圖(a)所示網的關鍵路徑：可見a2、a5和a7為關鍵活動，組成一條從源點到匯點的關鍵路徑，如圖(b)所示。

圖(a)所示網的計算結果:

4. 最短路徑

     最短路徑問題是圖的又一個比較典型的應用問題。例如，某一地區的一個公路網，給定了該網內的n 個城市以及這些城市之間的相通公路的距離，能否找到城市A 到城市B 之間一條舉例最近的通路呢？

如果將城市用點表示，城市間的公路用邊表示，公路的長度作為邊的權值，那么，這個問題就可歸結為在網圖中，求點A 到點B 的所有路徑中，邊的權值之和最短的那一條路徑。這條路徑就是兩點之間的最短路徑，并稱路徑上的第一個頂點為源點（Sourse），最后一個頂點為終點（Destination）。

單源點的最短路徑問題：給定帶權有向圖G＝（V，E）和源點v∈V，求從v 到G 中其余各頂點的最短路徑。在下面的討論中假設源點為v0。

解決問題的迪杰斯特拉算法：

即由迪杰斯特拉（Dijkstra）提出的一個按路徑長度遞增的次序產生最短路徑的算法。首先求出長度最短的一條最短路徑，然后參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。

算法的基本思想是：

設置兩個頂點的集合S 和T＝V－S，集合S 中存放已找到最短路徑的頂點，集合T 存放當前還未找到最短路徑的頂點。

初始狀態時，集合S 中只包含源點v0，然后不斷從集合T 中選取到頂點v0 路徑長度最短的頂點u 加入到集合S 中，集合S 每加入一個新的頂點u，都要修改頂點v0 到集合T 中剩余頂點的最短路徑長度值，集合T 中各頂點新的最短路徑長度值為原來的最短路徑長度值與頂點u 的最短路徑長度值加上u 到該頂點的路徑長度值中的較小值。此過程不斷重復，直到集合T 的頂點全部加入到S 中為止。
Dijkstra 算法的實現:

首先，引進一個輔助向量D，它的每個分量D[i] 表示當前所找到的從始點v 到每個終點vi 的最短路徑的長度。它的初態為：若從v 到vi 有弧，則D[i]為弧上的權值；否則置D[i]為∞。顯然，長度為：

D[j]=Min{D[i]| vi∈V}

的路徑就是從v 出發的長度最短的一條最短路徑。此路徑為（v ,vj）。
那么，下一條長度次短的最短是哪一條呢？假設該次短路徑的終點是vk ，則可想而知，這條路徑或者是（v, vk），或者是（v, vj, vk）。它的長度或者是從v 到vk 的弧上的權值，或者是D[j]和從vj 到vk 的弧上的權值之和。
依據前面介紹的算法思想，在一般情況下，下一條長度次短的最短路徑的長度必是：

D[j]=Min{D[i]| vi∈V-S}

其中，D[i] 或者弧（v, vi）上的權值，或者是D[k]( vk∈S 和弧（vk, vi）上的權值之和。
根據以上分析，可以得到如下描述的算法：
（1）假設用帶權的鄰接矩陣edges 來表示帶權有向圖，edges[i][j] 表示弧〈vi, vj〉上的權值。若〈vi, vj〉不存在，則置edges[i][j]為∞（在計算機上可用允許的最大值代替）。S 為已找到從v 出發的最短路徑的終點的集合，它的初始狀態為空集。那么，從v 出發到圖上其余各頂點（終點）vi 可能達到最短路徑長度的初值為：

D[i]= edges[Locate Vex(G,v)][i] vi∈V

（2）選擇vj，使得

D[j]=Min{D[i]| vi∈V-S}

vj 就是當前求得的一條從v 出發的最短路徑的終點。令

S＝S∪{j}

（3）修改從v 出發到集合V-S 上任一頂點vk 可達的最短路徑長度。如果

D[j]+ edges[j][k]<D[k]

則修改D[k]為

D[k]=D[j]+ edges[j][k]

重復操作（2）、（3）共n-1 次。由此求得從v 到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。

如圖8.26 所示一個有向網圖G8 的帶權鄰接矩陣為：

有向網圖G8 的帶權鄰接矩陣

用C 語言描述的Dijkstra 算法：

void ShortestPath_DIJ(MGraph G，int v0，PathMatrix &P，ShortPathTable &D){  
    //用Dijkstra算法求有向網G的v0頂點到其余頂點v的最短路徑P[v]及其帶權長度D[v]。  
    //若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點。  
    //final[v]為TRUE當且僅當v∈S，即已經求得從v0到v的最短路徑。   
      for(v=0； v<G.vexnum； ++v) {  
        final[v]=FALSE； D[v]=G.arcs[v0][v]；  
        for(w=0； w<G.vexnum； ++w) P[v][w] = FALSE；//設空路徑   
        if (D[v]<INFINITY) { P[v][v0]=TRUE； P[v][v]=TRUE；}  
      }//for  
      D[v0] = 0； final[v0] = TRUE； //初始化，v0頂點屬于S集   
    //開始主循環，每次求得v0到某個v頂點的最短路徑，并加v到s集。   
      for(i=1; i<G.vexnum；++i){ //其余G.vexnum-1個頂點  
        min = INFINITY； //當前所知離v0頂點的最近距離  
        for(w=0；w<G.vexnum；++w)  
          if(!final[w]) //w頂點在V-S中  
            if(D[w]<min){v=w；min=D[w]；} //w頂點離v0頂點更近  
        final[v]=TRUE； //離v0頂點最近的v加入S集  
        for(w=0；w<G.vexnum；++w) //更新當前最短路徑及距離  
          if(!final[w]&&(min+G.arcs[v][w]<D[w])){ //修改D[w]和P[w]  
            D[w]=min+G.arcs[v][w]；P[w]=P[v]； P[w][w]=TRUE； //P[w]=P[v]+[w]  
          }//if  
        }//for  
    }//ShortestPath_DIJ

轉自：http://blog.csdn.net/hguisu/article/details/7719428