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];
}