djstl算法?
发布网友
发布时间：2022-04-26 09:17
共1个回答
热心网友
时间：2022-06-26 14:22
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.baidu.com/view/7839.htm
http://ke.baidu.com/view/1939816.htm
