詳解圖的運用（最小生成樹、拓撲排序、症結途徑、最短途徑）。本站提示廣大學習愛好者：（詳解圖的運用（最小生成樹、拓撲排序、症結途徑、最短途徑））文章只能為提供參考，不一定能成為您想要的結果。以下是詳解圖的運用（最小生成樹、拓撲排序、症結途徑、最短途徑）正文
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
假定網中有n個極點，則第一個停止初始化的輪回語句的頻度為n，第二個輪回語句的頻度為n-1。個中有兩個內輪回：其一是在closedge[v].lowcost中求最小值，其頻度為n-1；其二是從新選擇具有最小價值的邊，其頻度為n。 由此，普裡姆算法的時光龐雜度為O(n2)，與網中的邊數有關，是以實用於求邊濃密的網的最小生成樹。
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網與拓撲排序：由偏序界說獲得拓撲有序的操作就是拓撲排序。樹立模子是AOV網
2. 1．AOV網(Activity on vertex network)
一切的工程或許某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為運動。若以圖中的極點來表現運動，有向邊（弧）表現運動之間的優先關系，則如許運動在極點上的有向圖稱為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)，而由偏序界說獲得拓撲有序的操作就是拓撲排序。
2.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網)：在AOE-網中有些運動可以並行地停止，所以完成工程的最短時光是從開端點到完成點的最長途徑的長度，途徑長度最長的途徑叫做症結途徑(Critical Path)。
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
以上就是圖的運用全體具體引見，願望對年夜家的進修有所贊助。
