词条 | 迪杰斯特拉算法 |
释义 | 定义及问题描述定义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. 对T中顶点的距离值进行修改:若加进W作中间顶点,从V0到Vi的 距离值比不加W的路径要短,则修改此距离值 重复上述步骤2、3,直到S中包含所有顶点,即S=T为止 迪杰斯特拉算法的原理首先,引进一个辅助向量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; //////////////////////////////////////////////////////////////////////////////// procedure 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; //////////////////////////////////////////////////////////////////////////////// procedure 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; //////////////////////////////////////////////////////////////////////////////// procedure 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。 三、代码 procedure 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; Dijkstra算法讲解与C/C++实现Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。 Dijkstra算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。 其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。 初始时,S中仅含有源。设u是G的某一个顶点,把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径,并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u,将u添加到S中,同时对数组dist作必要的修改。一旦S包含了所有V中顶点,dist就记录了从源到所有其它顶点之间的最短路径长度。 例如,对下图中的有向图,应用Dijkstra算法计算从源顶点1到其它顶点间最短路径的过程列在下表中。 主题好好理解上图! 以下是具体的实现(C/C++): /*************************************** * About: 有向图的Dijkstra算法实现 * Author: Tanky Woo ***************************************/ #include <iostream> using namespace std; const int maxnum = 100; const int maxint = 999999; // 各数组都从下标1开始 int dist[maxnum]; // 表示当前点到源点的最短路径长度 int prev[maxnum]; // 记录当前点的前一个结点 int c[maxnum][maxnum]; // 记录图的两点间路径长度 int n, line; // 图的结点数和路径数 // n -- n nodes // v -- the source node // dist[ ] -- the distance from the ith node to the source node // prev[ ] -- the previous node of the ith node // c[ ][ ] -- every two nodes' distance void Dijkstra(int n, int v, int *dist, int *prev, int c[maxnum][maxnum]) { bool s[maxnum]; // 判断是否已存入该点到S集合中 for(int i=1; i<=n; ++i) { dist[i] = c[v][i]; s[i] = 0; // 初始都未用过该点 if(dist[i] == maxint) prev[i] = 0; else prev[i] = v; } dist[v] = 0; s[v] = 1; // 依次将未放入S集合的结点中,取dist[]最小值的结点,放入结合S中 // 一旦S包含了所有V中顶点,dist就记录了从源点到所有其他顶点之间的最短路径长度 // 注意是从第二个节点开始,第一个为源点 for(int i=2; i<=n; ++i) { int tmp = maxint; int u = v; // 找出当前未使用的点j的dist[j]最小值 for(int j=1; j<=n; ++j) if((!s[j]) && dist[j]<tmp) { u = j; // u保存当前邻接点中距离最小的点的号码 tmp = dist[j]; } s[u] = 1; // 表示u点已存入S集合中 // 更新dist for(int j=1; j<=n; ++j) if((!s[j]) && c[u][j]<maxint) { int newdist = dist[u] + c[u][j]; if(newdist < dist[j]) { dist[j] = newdist; prev[j] = u; } } } } // 查找从源点v到终点u的路径,并输出 void searchPath(int *prev,int v, int u) { int que[maxnum]; int tot = 1; que[tot] = u; tot++; int tmp = prev[u]; while(tmp != v) { que[tot] = tmp; tot++; tmp = prev[tmp]; } que[tot] = v; for(int i=tot; i>=1; --i) if(i != 1) cout << que[i] << " -> "; else cout << que[i] << endl; } int main() { freopen("input.txt", "r", stdin); // 各数组都从下标1开始 // 输入结点数 cin >> n; // 输入路径数 cin >> line; int p, q, len; // 输入p, q两点及其路径长度 // 初始化c[][]为maxint for(int i=1; i<=n; ++i) for(int j=1; j<=n; ++j) c[i][j] = maxint; for(int i=1; i<=line; ++i) { cin >> p >> q >> len; if(len < c[p][q]) // 有重边 { c[p][q] = len; // p指向q c[q][p] = len; // q指向p,这样表示无向图 } } for(int i=1; i<=n; ++i) dist[i] = maxint; for(int i=1; i<=n; ++i) { for(int j=1; j<=n; ++j) printf("%8d", c[i][j]); printf("\"); } Dijkstra(n, 1, dist, prev, c); // 最短路径长度 cout << "源点到最后一个顶点的最短路径长度: " << dist[n] << endl; // 路径 cout << "源点到最后一个顶点的路径为: "; searchPath(prev, 1, n); } 输入数据: 5 7 1 2 10 1 4 30 1 5 100 2 3 50 3 5 10 4 3 20 4 5 60 输出数据: 999999 10 999999 30 100 10 999999 50 999999 999999 999999 50 999999 20 10 30 999999 20 999999 60 100 999999 10 60 999999 源点到最后一个顶点的最短路径长度: 60 源点到最后一个顶点的路径为: 1 -> 4 -> 3 -> 5 最后给出两道题目练手,都是直接套用模版就OK的: 1.HDOJ 1874 畅通工程续 2.HDOJ 2544 最短路 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。