迪傑斯特拉演算法例題
『壹』 【數據結構】最短路徑之迪傑斯特拉(Dijkstra)演算法與弗洛伊德(Floyd)演算法
迪傑斯特拉(Dijkstra)演算法核心： 按照路徑長度遞增的次序產生最短路徑。
迪傑斯特拉(Dijkstra)演算法步驟：（求圖中v0到v8的最短路徑）並非一下子求出v0到v8的最短路徑，而是 一步一步求出它們之間頂點的最短路徑 ，過過程中都是 基於已經求出的最短路徑的基礎上，求得更遠頂點的最短路徑，最終得出源點與終點的最短路徑 。
弗洛伊德(Floyd)演算法是一個經典的 動態規劃演算法 。
『貳』 迪傑斯特拉演算法的原理
1.首先，引入一個輔助向量D，它的每個分量 D 表示當前所找到的從起始點 （即源點 ）到其它每個頂點 的長度。
例如，D[3] = 2表示從起始點到頂點3的路徑相對最小長度為2。這里強調相對就是說在演算法執行過程中D的值是在不斷逼近最終結果但在過程中不一定就等於長度。
2.D的初始狀態為：若從 到 有弧（即從 到 存在連接邊），則D 為弧上的權值（即為從 到 的邊的權值）；否則置D 為∞。
顯然，長度為 D = Min{ D | ∈V } 的路徑就是從 出發到頂點 的長度最短的一條路徑，此路徑為( )。
3.那麼，下一條長度次短的是哪一條呢？也就是找到從源點 到下一個頂點的最短路徑長度所對應的頂點，且這條最短路徑長度僅次於從源點 到頂點 的最短路徑長度。
假設該次短路徑的終點是 ，則可想而知，這條路徑要麼是( )，或者是( )。它的長度或者是從 到 的弧上的權值，或者是D 加上從 到 的弧上的權值。
4.一般情況下，假設S為已求得的從源點 出發的最短路徑長度的頂點的集合，則可證明：下一條次最短路徑（設其終點為 ）要麼是弧( )，或者是從源點 出發的中間只經過S中的頂點而最後到達頂點 的路徑。
因此，下一條長度次短的的最短路徑長度必是D = Min{ D | ∈V-S }，其中D 要麼是弧( )上的權值，或者是D ( ∈S)和弧( , )上的權值之和。
演算法描述如下：
1）令arcs表示弧上的權值。若弧不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到的從 出發的的終點的集合，初始狀態為空集。那麼，從 出發到圖上其餘各頂點 可能達到的長度的初值為D=arcs[Locate Vex(G, )]， ∈V；
2）選擇 ，使得D =Min{ D | ∈V-S } ；
3）修改從 出發的到集合V-S中任一頂點 的最短路徑長度。
『叄』 djstl演算法
定義Dijkstra(迪傑斯特拉)演算法是典型的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN,
CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
問題描述在無向圖
G=(V,E) 中，假設每條邊 E[i] 的長度為 w[i]，找到由頂點 V0 到其餘各點的最短路徑。（單源最短路徑）
編輯本段迪傑斯特拉演算法迪傑斯特拉(Dijkstra)演算法思想
按路徑長度遞增次序產生最短路徑演算法：
把V分成兩組：
（1）S：已求出最短路徑的頂點的集合
（2）V-S=T：尚未確定最短路徑的頂點集合
將T中頂點按最短路徑遞增的次序加入到S中，
保證：（1）從源點V0到S中各頂點的最短路徑長度都不大於
從V0到T中任何頂點的最短路徑長度
（2）每個頂點對應一個距離值
S中頂點：從V0到此頂點的最短路徑長度
T中頂點：從V0到此頂點的只包括S中頂點作中間
頂點的最短路徑長度
依據：可以證明V0到T中頂點Vk的最短路徑，或是從V0到Vk的
直接路徑的權值；或是從V0經S中頂點到Vk的路徑權值之和
（反證法可證）
求最短路徑步驟
演算法步驟如下：
1. 初使時令 S={V0},T={其餘頂點}，T中頂點對應的距離值
若存在<V0,Vi>，d(V0,Vi)為<V0,Vi>弧上的權值
若不存在<V0,Vi>，d(V0,Vi)為∝
2. 從T中選取一個其距離值為最小的頂點W且不在S中，加入S
3. 對S中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的
距離值縮短，則修改此距離值
重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止
編輯本段迪傑斯特拉演算法的原理首先，引進一個輔助向量D，它的每個分量D表示當前所找到的從始點v到每個終點vi的最短路徑的長度。如D[3]=2表示從始點v到終點3的路徑相對最小長度為2。這里強調相對就是說在演算法過程中D的值是在不斷逼近最終結果但在過程中不一定就等於最短路徑長度。它的初始狀態為：若從v到vi有弧，則D為弧上的權值；否則置D為∞。顯然，長度為
D[j]=Min{D | vi∈V} 的路徑就是從v出發的長度最短的一條最短路徑。此路徑為(v,vj)。
那麼，下一條長度次短的最短路徑是哪一條呢？假設該次短路徑的終點是vk，則可想而知，這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是D[j]和從vj到vk的弧上的權值之和。
一般情況下，假設S為已求得最短路徑的終點的集合，則可證明：下一條最短路徑（設其終點為X）或者是弧(v,x)，或者是中間只經過S中的頂點而最後到達頂點X的路徑。因此，下一條長度次短的最短路徑的長度必是D[j]=Min{D
| vi∈V-S} 其中，D或者是弧(v,vi)上的權值，或者是D[k](vk∈S)和弧(vk,vi)上的權值之和。 迪傑斯特拉演算法描述如下：
1）arcs表示弧上的權值。若不存在，則置arcs為∞（在本程序中為MAXCOST）。S為已找到從v出發的最短路徑的終點的集合，初始狀態為空集。那麼，從v出發到圖上其餘各頂點vi可能達到的最短路徑長度的初值為D=arcs[Locate
Vex(G,v),i] vi∈V 2）選擇vj，使得D[j]=Min{D | vi∈V-S} 3）修改從v出發到集合V-S上任一頂點vk可達的最短路徑長度。
編輯本段迪傑斯特拉演算法C#程序public class Edge
{
public string StartNodeID ;
public string EndNodeID ;
public double Weight ; //權值，代價
} 節點則抽象成Node類，一個節點上掛著以此節點作為起點的「出邊」表。
public class Node
{
private string iD ;
private ArrayList edgeList ;//Edge的集合－－出邊表
public Node(string id )
{
this.iD = id ;
this.edgeList = new ArrayList() ;
}
property#region property
public string ID
{
get
{
return this.iD ;
}
}
public ArrayList EdgeList
{
get
{
return this.edgeList ;
}
}
#endregion
}
在計算的過程中，我們需要記錄到達每一個節點權值最小的路徑，這個抽象可以用PassedPath類來表示：
/// <summary>
/// PassedPath 用於緩存計算過程中的到達某個節點的權值最小的路徑
/// </summary>
public class PassedPath
{
private string curNodeID ;
private bool beProcessed ; //是否已被處理
private double weight ; //累積的權值
private ArrayList passedIDList ; //路徑
public PassedPath(string ID)
{
this.curNodeID = ID ;
this.weight = double.MaxValue ;
this.passedIDList = new ArrayList() ;
this.beProcessed = false ;
}
#region property
public bool BeProcessed
{
get
{
return this.beProcessed ;
}
set
{
this.beProcessed = value ;
}
}
public string CurNodeID
{
get
{
return this.curNodeID ;
}
}
public double Weight
{
get
{
return this.weight ;
}
set
{
this.weight = value ;
}
}
public ArrayList PassedIDList
{
get
{
return this.passedIDList ;
}
}
#endregion
}
另外，還需要一個表PlanCourse來記錄規劃的中間結果，即它管理了每一個節點的PassedPath。
/// <summary>
/// PlanCourse 緩存從源節點到其它任一節點的最小權值路徑=》路徑表
/// </summary>
public class PlanCourse
{
private Hashtable htPassedPath ;
#region ctor
public PlanCourse(ArrayList nodeList ,string originID)
{
this.htPassedPath = new Hashtable() ;
Node originNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
originNode = node ;
}
else
{
PassedPath pPath = new PassedPath(node.ID) ;
this.htPassedPath.Add(node.ID ,pPath) ;
}
}
if(originNode == null)
{
throw new Exception("The origin node is not exist !")
;
}
this.InitializeWeight(originNode) ;
}
private void InitializeWeight(Node originNode)
{
if((originNode.EdgeList == null)
||(originNode.EdgeList.Count == 0))
{
return ;
}
foreach(Edge edge in originNode.EdgeList)
{
PassedPath pPath = this[edge.EndNodeID] ;
if(pPath == null)
{
continue ;
}
pPath.PassedIDList.Add(originNode.ID) ;
pPath.Weight = edge.Weight ;
}
}
#endregion
public PassedPath this[string nodeID]
{
get
{
return (PassedPath)this.htPassedPath[nodeID] ;
}
}
}
在所有的基礎構建好後，路徑規劃演算法就很容易實施了，該演算法主要步驟如下：
(1)用一張表(PlanCourse)記錄源點到任何其它一節點的最小權值，初始化這張表時，如果源點能直通某節點，則權值設為對應的邊的權，否則設為double.MaxValue。
(2)選取沒有被處理並且當前累積權值最小的節點TargetNode，用其邊的可達性來更新到達其它節點的路徑和權值（如果其它節點
經此節點後權值變小則更新，否則不更新），然後標記TargetNode為已處理。
(3)重復(2)，直至所有的可達節點都被處理一遍。
(4)從PlanCourse表中獲取目的點的PassedPath，即為結果。
下面就來看上述步驟的實現，該實現被封裝在RoutePlanner類中：
/// <summary>
/// RoutePlanner 提供圖演算法中常用的路徑規劃功能。
/// 2005.09.06
/// </summary>
public class RoutePlanner
{
public RoutePlanner()
{
}
#region Paln
//獲取權值最小的路徑
public RoutePlanResult Paln(ArrayList nodeList ,string
originID ,string destID)
{
PlanCourse planCourse = new PlanCourse(nodeList
,originID) ;
Node curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;
#region 計算過程
while(curNode != null)
{
PassedPath curPath = planCourse[curNode.ID] ;
foreach(Edge edge in curNode.EdgeList)
{
PassedPath targetPath = planCourse[edge.EndNodeID] ;
double tempWeight = curPath.Weight + edge.Weight ;
if(tempWeight < targetPath.Weight)
{
targetPath.Weight = tempWeight ;
targetPath.PassedIDList.Clear() ;
for(int i=0 ;i<curPath.PassedIDList.Count ;i++)
{
targetPath.PassedIDList.Add(curPath.PassedIDList.ToString())
;
}
targetPath.PassedIDList.Add(curNode.ID) ;
}
}
//標志為已處理
planCourse[curNode.ID].BeProcessed = true ;
//獲取下一個未處理節點
curNode = this.GetMinWeightRudeNode(planCourse
,nodeList ,originID) ;
}
#endregion
//表示規劃結束
return this.GetResult(planCourse ,destID) ;
}
#endregion
#region private method
#region GetResult
//從PlanCourse表中取出目標節點的PassedPath，這個PassedPath即是規劃結果
private RoutePlanResult GetResult(PlanCourse
planCourse ,string destID)
{
PassedPath pPath = planCourse[destID] ;
if(pPath.Weight == int.MaxValue)
{
RoutePlanResult result1 = new RoutePlanResult(null
,int.MaxValue) ;
return result1 ;
}
string[] passedNodeIDs = new
string[pPath.PassedIDList.Count] ;
for(int i=0 ;i<passedNodeIDs.Length ;i++)
{
passedNodeIDs = pPath.PassedIDList.ToString() ;
}
RoutePlanResult result = new
RoutePlanResult(passedNodeIDs ,pPath.Weight) ;
return result ;
}
#endregion
#region GetMinWeightRudeNode
//從PlanCourse取出一個當前累積權值最小，並且沒有被處理過的節點
private Node GetMinWeightRudeNode(PlanCourse
planCourse ,ArrayList nodeList ,string originID)
{
double weight = double.MaxValue ;
Node destNode = null ;
foreach(Node node in nodeList)
{
if(node.ID == originID)
{
continue ;
}
PassedPath pPath = planCourse[node.ID] ;
if(pPath.BeProcessed)
{
continue ;
}
if(pPath.Weight < weight)
{
weight = pPath.Weight ;
destNode = node ;
}
}
return destNode ;
}
#endregion
#endregion
}
編輯本段迪傑斯特拉演算法pascal程序type bool=array[1..10]of
boolean;
arr=array[0..10]of integer;
var a:array[1..10,1..10]of integer;
//存儲圖的鄰接數組，無邊為10000
c,d,e:arr; //c為最短路徑數值,d為各點前趨,
t:bool; //e：路徑，t為輔助數組
i,j,n,m:integer;
inf,outf:text;
////////////////////////////////////////////////////////////////////////////////
procere init; //不同題目鄰接數組建立方式不一樣
begin
assign(inf,'dijkstra.in');
assign(outf,'dijkstra.out');
reset(inf); rewrite(outf);
read(inf,n);
for i:=1 to n do
for j:=1 to n do
begin
read(inf,a[i,j]);
if a[i,j]=0 then a[i,j]:=10000;
end;
end;
////////////////////////////////////////////////////////////////////////////////
procere dijkstra(qi:integer; t:bool; var c{,d}:arr);
//qi起點，{}中為求路徑部
var i,j,k,min:integer; //分,不需求路徑時可以不要
begin //t數組一般在調用前初始
t[qi]:=true; //化成false,也可將部分點
{for i:=1 to n do d[i]:=qi; d[qi]:=0; }
//初始化成true以迴避這些點
for i:=1 to n do c[i]:=a[qi,i];
for i:=1 to n-1 do
begin
min:=10001;
for j:=1 to n do
if (c[j]<min)and(not(t[j])) then begin k:=j;
min:=c[j];end;
t[k]:=true;
for j:=1 to n do
if (c[k]+a[k,j]<c[j])and(not(t[j])) then
begin
c[j]:=c[k]+a[k,j]; {d[j]:=k;}
end;
end;
end;
////////////////////////////////////////////////////////////////////////////////
procere make(zh:integer; d:arr; var e:arr);
//生成路徑,e[0]保存路徑
var i,j,k:integer; //上的節點個數
begin
i:=0;
while d[zh]<>0 do
begin
inc(i);e[i]:=zh;zh:=d[zh];
end;
inc(i);e[i]:=qi; e[0]:=I;
end;
主程序調用：求最短路徑長度：初始化t，然後dijkstra(qi,t,c,d)
求路徑：make(m,d,e) ，m是終點
編輯本段Dijkstra演算法的堆優化(PASCAL實現)一、思考
我們可以發現，在實現步驟時，效率較低(需要O(n)，使總復雜度達到O(n^2)。對此可以考慮用堆這種數據結構進行優化，使此步驟復雜度降為O(log(n))(總復雜度降為O(n
log(n))。
二、實現
1. 將與源點相連的點加入堆，並調整堆。
2. 選出堆頂元素u（即代價最小的元素），從堆中刪除，並對堆進行調整。
3. 處理與u相鄰的，未被訪問過的，滿足三角不等式的頂點
1):若該點在堆里，更新距離，並調整該元素在堆中的位置。
2):若該點不在堆里，加入堆，更新堆。
4. 若取到的u為終點，結束演算法；否則重復步驟2、3。
三、代碼
procere Dijkstra;
var
u,v,e,i:longint;
begin
fillchar(dis,sizeof(dis),$7e); //距離
fillchar(Inh,sizeof(Inh),false); //是否在堆中
fillchar(visit,sizeof(visit),false); //是否訪問過
size:=0;
e:=last[s];
while e<>0 do //步驟1
begin
u:=other[e];
if not(Inh[u]) then //不在堆里
begin
inc(size);
heap[size]:=u;
dis[u]:=cost[e];
Loc[u]:=size; //Loc數組記錄元素在堆中的位置
Inh[u]:=true;
Shift_up(Loc[u]); //上浮
end
else
if cost[e]<dis[u] then //在堆里
begin
dis[u]:=cost[e];
Shift_up(Loc[u]);
Shift_down(Loc[u]);
end;
e:=pre[e];
end;
visit[s]:=true;
while true do
begin
u:=heap[1]; //步驟2
if u=t then break; //步驟4
visit[u]:=true;
heap[1]:=heap[size];
dec(size);
Shift_down(1);
e:=last[u];
while e<>0 do //步驟3
begin
v:=other[e];
if Not(visit[v]) and (dis[u]+cost[e]<dis[v]) then
//與u相鄰的，未被訪問過的，滿足三角不等式的頂點
if Inh[v] then //在堆中
begin
dis[v]:=dis[u]+cost[e];
Shift_up(Loc[v]);
Shift_Down(Loc[v]);
end
else //不再堆中
begin
inc(size);
heap[size]:=v;
dis[v]:=dis[u]+cost[e];
Loc[v]:=size;
Inh[v]:=true;
Shift_up(Loc[v]);
end;
e:=pre[e];
end;
end;
writeln(dis[t]);
end;
http://ke..com/view/7839.htm
http://ke..com/view/1939816.htm
『肆』 求有向圖兩個頂點間的最短路徑的方法，用簡單語言或舉例描述。
在交通網路中，常常會提出許多這樣的問題：兩地之間是否有路相通？在有多條通路的情況下，哪一條最近？哪一條花費最少等。交通網路可以用帶權圖表示，圖中頂點表示域鎮，邊表示兩城之間的道路，邊上權值可表示兩城鎮間的距離，交通費用或途中所需的時間等。
以上提出的問題就是帶權圖中求最短路徑的問題，即求兩個頂點間長度最短的路徑。
最短路徑問題的提法很多。在這里僅討論單源最短路徑問題：即已知有向圖(帶權)，我們希望找出從某個源點S∈V到G中其餘各頂點的最短路徑。
例如：下圖(有向圖G14)，假定以v1為源點，則其它各頂點的最短路徑如下表所示：
圖 G14
從有向圖可看出，頂點v1到v4的路徑有3條：(v1,v2,v4)，(v1,v4)，(v1,v3,v2,v4 )，其路徑長度分別為：15,20和10。因此v1到v4的最短路徑為(v1,v3,v2,v4 )。
為了敘述方便，我們把路徑上的開始點稱為源點，路徑的最後一個頂點為終點。
那麼，如何求得給定有向圖的單源最短路徑呢？迪傑斯特拉(Dijkstra)提出按路徑長度遞增產生諸頂點的最短路徑演算法，稱之為迪傑斯特拉演算法。
迪傑斯特拉演算法求最短路徑的實現思想是：設有向圖G=(V,E)，其中，V={1,2,…,n}，cost是表示G的鄰接矩陣，cost[i][j] 表示有向邊<i,j>的權。若不存在有向邊<i,j>，則cost[i][j]的權為無窮大(這里取值為32767)。設S是一個集合，其中的每個元素表示一個頂點，從源點到這些頂點的最短距離已經求出。設頂點v1為源點，集合S的初態只包含頂點v1。數組dist記錄從源點到其他各頂點當前的最短距離，其初值為dist[i]=cost[v1][i]，i=2,…,n。從S之外的頂點集合V-S 中選出一個頂點w，使dist[w]的值最小。於是從源點到達w只通過S 中的頂點，把w加入集合S中調整dist中記錄的從源點到V-S中每個頂點v的距離：從原來的dist[v] 和dist[w]+cost[w][v]中選擇較小的值作為新的dist[v]。重復上述過程，直到S中包含V中其餘頂點的最短路徑。
最終結果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數組dist記錄了從源點到 V中其餘各頂點之間的最短路徑，path是最短路徑的路徑數組，其中path[i] 表示從源點到頂點i之間的最短路徑的前驅頂點。