dijkstra演算法用什麼數據結構

❶ Dijkstra演算法時間復雜度

我們可以用大O符號將Dijkstra演算法的運行時間表示為邊數m和頂點數n的函數。

Dijkstra演算法最簡單的實現方法是用一個鏈表或者數組來存儲所有頂點的集合Q,所以搜索Q中最小元素的運算(Extract-Min(Q))只需要線性搜索Q中的所有元素。這樣的話演算法的運行時間是O(n2)。

對於邊數少於n2稀疏圖來說，我們可以用鄰接表來更有效的實現Dijkstra演算法。同時需要將一個二叉堆或者斐波納契堆用作優先隊列來尋找最小的頂點(Extract-Min)。當用到二叉堆的時候，演算法所需的時間為O((m+n)log n)，斐波納契堆能稍微提高一些性能，讓演算法運行時間達到O(m + n log n)。相關問題和演算法

在Dijkstra演算法的基礎上作一些改動，可以擴展其功能。例如，有時希望在求得最短路徑的基礎上再列出一些次短的路徑。為此，可先在原圖上計算出最短路徑，然後從圖中刪去該路徑中的某一條邊，在餘下的子圖中重新計算最短路徑。對於原最短路徑中的每一條邊，均可求得一條刪去該邊後子圖的最短路徑，這些路徑經排序後即為原圖的一系列次短路徑。

OSPF（open shortest path first, 開放最短路徑優先）演算法是Dijkstra演算法在網路路由中的一個具體實現。
與Dijkstra演算法不同，Bellman-Ford演算法可用於具有負花費邊的圖，只要圖中不存在總花費為負值且從源點 s 可達的環路（如果有這樣的環路，則最短路徑不存在，因為沿環路循環多次即可無限制的降低總花費）。

與最短路徑問題有關的一個問題是旅行商問題(traveling salesman problem)，它要求找出通過所有頂點恰好一次且最終回到源點的最短路徑。該問題是NP難的；換言之，與最短路徑問題不同，旅行商問題不太可能具有多項式時間演算法。

如果有已知信息可用來估計某一點到目標點的距離，則可改用A*演算法，以減小最短路徑的搜索范圍。

❷ 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

❸ Dijkstrath演算法是什麼如何用Dijkstrath演算法求計算機網路拓撲圖的最短路徑

Dijkstra演算法是典型 的單源最短路徑演算法，用於計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra演算法是很有代表性的最短路徑演算法，在很多專業課程中都作為基本內容有詳細的介紹，如數據結構，圖論，運籌學等等。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用OPEN, CLOSE表的方式，這里均採用永久和臨時標號的方式。注意該演算法要求圖中不存在負權邊。
迪傑斯特拉(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. 對其餘T中頂點的距離值進行修改：若加進W作中間頂點，從V0到Vi的

距離值縮短，則修改此距離值

重復上述步驟2、3，直到S中包含所有頂點，即W=Vi為止

❹ 單源最短路徑的Dijkstra演算法

將圖G中所有的頂點V分成兩個頂點集合S和T。以v為源點已經確定了最短路徑的終點並入S集合中，S初始時只含頂點v,T則是尚未確定到源點v最短路徑的頂點集合。然後每次從T集合中選擇S集合點中到T路徑最短的那個點，並加入到集合S中，並把這個點從集合T刪除。直到T集合為空為止。
具體步驟
1、選一頂點v為源點，並視從源點v出發的所有邊為到各頂點的最短路徑（確定數據結構：因為求的是最短路徑，所以①就要用一個記錄從源點v到其它各頂點的路徑長度數組dist[],開始時，dist是源點v到頂點i的直接邊長度，即dist中記錄的是鄰接陣的第v行。②設一個用來記錄從源點到其它頂點的路徑數組path[],path中存放路徑上第i個頂點的前驅頂點）。
2、在上述的最短路徑dist[]中選一條最短的，並將其終點（即<v,k>）k加入到集合s中。
3、調整T中各頂點到源點v的最短路徑。 因為當頂點k加入到集合s中後，源點v到T中剩餘的其它頂點j就又增加了經過頂點k到達j的路徑,這條路徑可能要比源點v到j原來的最短的還要短。調整方法是比較dist[k]+g[k,j]與dist[j]，取其中的較小者。
4、再選出一個到源點v路徑長度最小的頂點k,從T中刪去後加入S中，再回去到第三步，如此重復，直到集合S中的包含圖G的所有頂點。 SPFA實際上是Bellman-Ford基礎上的隊列優化
SPFA(G,w,s)
1. INITIALIZE-SINGLE-SOURCE(G,s)
2. INITIALIZE-QUEUE(Q)
3. ENQUEUE(Q,s)
4. While Not EMPTY(Q)
5. Do u<-DLQUEUE(Q)
6. For 每條邊(u,v) in E[G]
7. Do tmp<-d[v]
8. Relax(u,v,w)
9. If (d[v] < tmp) and (v不在Q中)
10. ENQUEUE(Q,v)
c++：
boolSPFA(intsource)
{
deque<int>dq;
inti,j,x,to;
for(i=1;i<=nodesum;i++)
{
in_sum[i]=0;
in_queue[i]=false;
dist[i]=INF;
path[i]=-1;
}
dq.push_back(source);
in_sum[source]++;
dist[source]=0;
in_queue[source]=true;
//初始化完成
while(!dq.empty())
{
x=dq.front();
dq.pop_front();
in_queue[x]=false;
for(i=0;i<adjmap[x].size();i++)
{
to=adjmap[x][i].to;
if((dist[x]<INF)&&(dist[to]>dist[x]+adjmap[x][i].weight))
{
dist[to]=dist[x]+adjmap[x][i].weight;
path[to]=x;
if(!in_queue[to])
{
in_queue[to]=true;
in_sum[to]++;
if(in_sum[to]==nodesum)
return false;
if(!dq.empty())
{
if(dist[to]>dist[dq.front()])
dq.push_back(to);
else
dq.push_front(to);
}
else
dq.push_back(to);
}
}
}
}
returntrue;
}

❺ C語言數據結構關於dijkstra演算法

你用一個數組 dist 記錄最短路徑長，用另一個數組 pre 記錄直接前驅。關鍵語句如下：
if (dist[j] > dist[i] + edge[i, j])
{
dist[j] = dist[i] + edge[i, j];
pre[j] = i;
}
這樣就行了。

❻ dijkstra演算法

[問題分析]
對於一個含有n個頂點和e條邊的圖來說，從某一個頂點Vi到其餘任一頂點Vj的最短路徑，可能是它們之間的邊（Vi，Vj），也可能是經過k個中間頂點和k+1條邊所形成的路徑(1≤k≤n-2)。下面給出解決這個問題的Dijkstra演算法思想。
設圖G用鄰接矩陣的方式存儲在GA中，GA[i,j]=maxint表示Vi，Vj是不關聯的，否則為權值（大於0的實數）。設集合S用來保存已求得最短路徑的終點序號，初始時S=[Vi]表示只有源點，以後每求出一個終點Vj，就把它加入到集合中並作為新考慮的中間頂點。設數組dist[1..n]用來存儲當前求得的最短路徑，初始時Vi，Vj如果是關聯的，則dist[j]等於權值，否則等於maxint，以後隨著新考慮的中間頂點越來越多，dist[j]可能越來越小。再設一個與dist對應的數組path[1..n]用來存放當前最短路徑的邊，初始時為Vi到Vj的邊，如果不存在邊則為空。
執行時，先從S以外的頂點（即待求出最短路徑的終點）所對應的dist數組元素中，找出其值最小的元素（假設為dist[m]），該元素值就是從源點Vi到終點Vm的最短路徑長度，對應的path[m]中的頂點或邊的序列即為最短路徑。接著把Vm並入集合S中，然後以Vm作為新考慮的中間頂點，對S以外的每個頂點Vj，比較dist[m]+GA[m,j]的dist[j]的大小，若前者小，表明加入了新的中間頂點後可以得到更好的方案，即可求得更短的路徑，則用它代替dist[j]，同時把Vj或邊（Vm，Vj）並入到path[j]中。重復以上過程n-2次，即可在dist數組中得到從源點到其餘各終點的最段路徑長度，對應的path數組中保存著相應的最段路徑。

下面給出具體的Dijkstra演算法框架（註：為了實現上的方便，用一個一維數組s[1..n]代替集合S，用來保存已求得最短路徑的終點集合，即如果s[j]=0表示頂點Vj不在集合中，反之，s[j]=1表示頂點Vj已在集合中）。
Procere Dijkstra(GA,dist,path,i)；
{表示求Vi到圖G中其餘頂點的最短路徑，GA為圖G的鄰接矩陣，dist和path為變數型參數，
其中path的基類型為集合}
Begin
For j:=1 To n Do Begin {初始化}
If j<>i Then s[j]:=0 Else s[j]:=1；
dist[j]:=GA[i,j]；
If dist[j]<maxint Then path[j]:=[i]+[j] Else path[j]:=[ ]；
End；
For k:=1 To n-2 Do
Begin
w:=maxint；m:=i；
For j:=1 To n Do {求出第k個終點Vm}
If (s[j]=0) and (dist[j]<w) Then Begin m:=j；w:=dist[j]； End；
If m<>i Then s[m]:=1 else exit；
{若條件成立，則把Vm加入到S中，
否則退出循環，因為剩餘的終點，其最短路徑長度均為maxint，無需再計算下去}
For j:=1 To n Do {對s[j]=0的更優元素作必要修改}
If (s[j]=0) and (dist[m]+GA[m,j]<dist[j])
Then Begin Dist[j]:=dist[m]+GA[m,j]；path[j]:=path[m]+[j]；End；
End；
End；

（1）從一個頂點到其餘各頂點的最短路徑
對於一個含有n個頂點和e條邊的圖來說，從某個頂點vi到其餘任一頂點vj的最短路徑，可能是它們之間的邊（vi，vj），也可能是經過k個中間點和k+1條邊所形成的路徑（1≤k ≤n-2）。
首先來分析Dijkstra的演算法思想
設圖G用鄰接矩陣的方式存儲在GA中，GA[I，j]=maxint表示vi，vj是不關聯的，否則為權值（大於0的實數）。設集合S用來存儲保存已求得最短路徑的終點序號，初始時S=[vi]表示只有源點，以後每求出一個終點vj，就把它加入到集合中並作為新考慮的中間頂點。設數組dist[1..n]用來存儲當前求得的最短路徑，初始時vi，vj如果是關聯的，則dist[j]等於權值，否則等於maxint，以後隨著新考慮的中間頂點越來越多，dist[j]可能越來越小。再設一個與dist對應的數組path[1..n]用來存放當前最短路徑的邊，初始時vi到vj的邊，如果不存在邊則為空。
執行時，先從S以外的頂點（即待求出最短路徑的終點）所對應的dist數組元素中，找出其值最小的元素（假設為dist[m]），該元素值就是從源點vi到終點vm的最短路徑長度，對應的path[m]中的頂點或邊的序列即為最短路徑。接著把vm並入集合S中，然後以vm作為新考慮的中間頂點，對S以外的每個頂點vj，比較dist[m]+GA[i，j]與dist[j]的大小，若前者小，表明加入了新的中間頂點後可以得到更好的方案，即可求得更短的路徑，則用它代替dist[j]，同時把vj或邊（vm，vj）並入到path[j]中。重復以上過程n-2次，即可在dist數組中得到從源點到其餘個終點的最短路徑長度，對應的path數組中保存著相應的最短路徑。
為了實現上的方便，用一個一維數組s[1..n]代替集合s，用來保存已求得最短路徑的終點集合，即如果s[j]=0表示頂點vj不在集合中，反之，s[j]表示頂點vj已在集合中）。

Procere dijkstra (GA,dist path,I)
begin
for j:= 1 to n do begin
if j<>I then s[j]:=0;{j不在集合中} else s[j]:=1;{j在集合中}；
dist[j]:=GA[I,J];
IF dist [j]<maxint {maxint為假設的一個足夠大的數}
Then path [j]:=[I]+[j]
Else path[j]:=[ ];
End;
For k:= 1 to n-1 do begin w:=maxint;m:=I;
For j:= 1 to n do{求出第k個終點Vm}
if (s[j]=0)and(dist[j]<w) then begin m:=j;w:=dist[j];end;
If m<>I then s[m]:=1 else exit;{若條件成立，則把Vm加入到s中，否則退出循環，因為
剩餘的終點，其最短路徑長度均為maxint，無需再計算下去}
for j:=1 to n do {對s[j]=0的更優元素作必要修改}
if (s[j]=0)and (dist[m]+GA[m,j]<dist[j])
then begin
dist[j]:=dist[m]+GA[m,j];
path[j]:=path[m]+[j];
End;
End;
End;

用集合的思想：

for k:=1 to n-1 do
begin
wm:=max;j:=0;
for i:=1 to n do
if not(i in s)and(dist[i]<wm) then begin j:=i;wm:=dist[i];end;
s:=s+[j];
for i:=1 to n do
if not(i in s)and(dist[j]+cost[j,i]<dist[i]) then
begin dist[i]:=dist[j]+cost[j,i];path[i]:=path[j]+char(48+i);end;
end;

❼ 數據結構課程設計 迪結斯特拉演算法

額，我這個寫的已經比較清楚了。是數組模擬鄰接表的，addedge裡面建立的是雙向邊。

鄰接矩陣的話。

cin>>n>>m;//n point m edge

for(int i=1;i<=m;i++)

{

cin>>from>>to>>value;

g[from][to] = value;

}

memset(dis,20,sizeof(dis));
dis[1]=0;
for(int i=1;i<=n;i++)
{
int p=0;
for(int j=1;j<=n;j++)
if(!u[j]&&(p==0||dis[j]<dis[p]))
p=j;
u[p]=false;
for(int j=1;j<=n;j++)
if(dis[p]+g[p][j]<dis[j])
dis[j]=dis[p]+g[p][j];
}