dijkstra算法优化
① 在解决最短路径优化问题中，Dijkstra算法有哪些优.缺点
优点：算法简明、能得到最优解
缺点：效率低（特别是有时候不需要最优解）、运算中占用空间大
② 图文解析 | Dijkstra单源最短路径算法
给定 加权有向图 G=(V,E,W)，每条边的权值w为 非负数 ，表示两个顶点间的距离。
源点s∈V。
求：从s出发到其他各个顶点的最短路径。
如上图所示，以1为源点，计算到其余各个顶点的最短距离（我已用红线标出）。下面列出了最终解：
S集合 ：当从s到x（x ∈V ）的最短路径找到时，则x ∈S。当所有顶点都进入S集合时，算法结束。
初始：S=｛s｝，当S=V时算法结束。
从s到u相对于S的最短路径 ：指从s到u且仅经过S中顶点的最短路径。
dist[u]:从s到u相对于S的最短路径长度
short[u]:从s到u最短路径的长度（算法最终解）
dist[u] ≥ short[u]
Dijkstra算法采用贪心算法模式，算法过程就是通过计算dist[u],不断扩充S集合，同时dist[u]会不断优化改善，直到dist[u] = short[u]，并将其放到S中，当所有顶点都放入S集合时，算法结束。
输入：加权有向图G=(V,E,W)
V={1,2,…,n}, s=1
输出：从s到每个顶点的最短路径
输入：G=(V,E,W)，源点1
V={1,2,3,4,5,6}
初始S集合只有1，计算直接从1能到达的顶点的距离，其他不能从1号顶点直接到达的顶点都记为无穷大。雀轮睁此时从dist[u]里找出最短距离的顶点（6号），并将其放进S集合。
S={1}
dist[1] = 0
dist[2] = 10
dist[6 ] = 3
dist[3] = ∞
dist[4] = ∞
dist[5] = ∞
当把6号顶点放进S集合后，经由6号顶点出发到达的顶点的最短距离可能会被优化更新，因为该算法的思想很“贪心”，谁更短我要谁！比如1->6->2要比1->2距离更短，所以dist[2]被更顷岁新为5，从专业术语上讲，这个“更新”过程叫做松弛，其他点同理。然桐唤后从dist[u]里找出最短的路径的那个顶点（5号），并放进S集合里。
S={1,6}
dist[1] = 0
dist[6] = 3
dist[2] = 5
dist[4] = 9
dist[5] = 4
dist[3] = ∞
后面的操作步骤其实就是重复上面的操作。即当S集合里有个新的顶点后，就可能会更新其他点的最短距离，更新一遍后，找出当前最短距离的dist[u]，并将该顶点放进S集合。后面不重复阐述。
S={1,6,5}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = ∞
S={1,6,5,2}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
S={1,6,5,2,4,3}
dist[1] = 0
dist[6] = 3
dist[5] = 4
dist[2] = 5
dist[4] = 9
dist[3] = 12
当有向图中的所有顶点都进入了S集合后，算法结束，此时的dist[u]的值其实就是最初我们找出的那个最终解short[u]，所以，算法结束时，dist[u]=short[u],得到最终解。
③ dijkstra算法是什么
迪杰斯特拉算法用来解决从顶点v0出发到其余顶点的最短路径，该算法按照最短路径长度递增的顺序产生所以最短路径。
对于图G=（V，E），将图中的顶点分成两组：第一组S：已求出的最短路径的终点集合（开始为｛v0}）。第二组V-S：尚未求出最短路径的终点集合（开始为V-{v0}的全部结点）。
堆优化
思考
该算法复杂度为n^2,我们可以发现，如果边数远小于n^2,对此可以考虑用堆这种数据结构进行优化，取出最短路径的复杂度降为O(1)；每次调整的复杂度降为O（elogn）；e为该点的边数，所以复杂度降为O((m+n)logn)。
实现
1、将源点加入堆，并调整堆。
2、选出堆顶元素u（即代价最小的元素），从堆中删除，并对堆进行调整。
3、处理与u相邻的，未被访问过的，满足三角不等式的顶点
1):若该点在堆里，更新距离，并调整该元素在堆中的位置。
2):若该点不在堆里，加入堆，更新堆。
4、若取到的u为终点，结束算法；否则重复步骤2、3。
④ 最短路径 | 深入浅出Dijkstra算法（一）
上次我们介绍了神奇的只有 五行的 Floyd-Warshall 最短路算法 ，它可以方便的求得 任意两点的最短路径， 这称为 “多源最短路”。
这次来介绍 指定一个点（源点）到其余各个顶点的最短路径， 也叫做 “单源最短路径”。 例如求下图中的 1 号顶点到 2、3、4、5、6 号顶点的最短路径。
与 Floyd-Warshall 算法一样，这里仍然 使用二维数组 e 来存储顶点之间边的关系， 初始值如下。
我们还需要用 一个一维数组 dis 来存储 1 号顶点到其余各个顶点的初始路程， 我们可以称 dis 数组为 “距离表”， 如下。
我们将此时 dis 数组中的值称为 最短路的“估计值”。
既然是 求 1 号顶点到其余各个顶点的最短路程， 那就 先找一个离 1 号顶点最近的顶点。
通过数组 dis 可知当前离 1 号顶点最近是 2 号顶点。 当选择了 2 号顶点后，dis[2]的值就已经从“估计值”变为了“确定值”， 即 1 号顶点到 2 号顶点的最短路程就是当前 dis[2]值。
为什么呢？你想啊， 目前离 1 号顶点最近的是 2 号顶点，并且这个图所有的边都是正数，那么肯定不可能通过第三个顶点中转，使得 1 号顶点到 2 号顶点的路程进一步缩短了。 因此 1 号顶点到其它顶点的路程肯定没有 1 号到 2 号顶点短，对吧 O(∩_∩)O~
既然选了 2 号顶点，接下来再来看 2 号顶点 有哪些 出边 呢。有 2->3 和 2->4 这两条边。
先讨论 通过 2->3 这条边能否让 1 号顶点到 3 号顶点的路程变短。 也就是说现在来比较 dis[3] 和 dis[2]+e[2][3] 的大小。其中 dis[3]表示 1 号顶点到 3 号顶点的路程，dis[2]+e[2][3]中 dis[2]表示 1 号顶点到 2 号顶点的路程，e[2][3]表示 2->3 这条边。所以 dis[2]+e[2][3]就表示从 1 号顶点先到 2 号顶点，再通过 2->3 这条边，到达 3 号顶点的路程。
我们发现 dis[3]=12，dis[2]+e[2][3]=1+9=10，dis[3]>dis[2]+e[2][3]，因此 dis[3]要更新为 10。这个过程有个专业术语叫做 “松弛” 。即 1 号顶点到 3 号顶点的路程即 dis[3]，通过 2->3 这条边 松弛成功。 这便是 Dijkstra 算法的主要思想： 通过 “边” 来松弛 1 号顶点到其余各个顶点的路程。
同理通过 2->4（e[2][4]），可以将 dis[4]的值从 ∞ 松弛为 4（dis[4]初始为 ∞，dis[2]+e[2][4]=1+3=4，dis[4]>dis[2]+e[2][4]，因此 dis[4]要更新为 4）。
刚才我们对 2 号顶点所有的出边进行了松弛。松弛完毕之后 dis 数组为：
接下来，继续在剩下的 3、4、5 和 6 号顶点中，选出离 1 号顶点最近的顶点。通过上面更新过 dis 数组，当前离 1 号顶点最近是 4 号顶点。此时，dis[4]的值已经从“估计值”变为了“确定值”。下面继续对 4 号顶点的所有出边（4->3，4->5 和 4->6）用刚才的方法进行松弛。松弛完毕之后 dis 数组为：
继续在剩下的 3、5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 3 号顶点。此时，dis[3]的值已经从“估计值”变为了“确定值”。对 3 号顶点的所有出边（3->5）进行松弛。松弛完毕之后 dis 数组为：
继续在剩下的 5 和 6 号顶点中，选出离 1 号顶点最近的顶点，这次选择 5 号顶点。此时，dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边（5->4）进行松弛。松弛完毕之后 dis 数组为：
最后对 6 号顶点的所有出边进行松弛。因为这个例子中 6 号顶点没有出边，因此不用处理。 到此，dis 数组中所有的值都已经从“估计值”变为了“确定值”。
最终 dis 数组如下，这便是 1 号顶点到其余各个顶点的最短路径。
OK，现在来总结一下刚才的算法。 Dijkstra算法的基本思想是：每次找到离源点（上面例子的源点就是 1 号顶点）最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。
基本步骤如下：
在 博客 中看到两个比较有趣的问题，也是在学习Dijkstra时，可能会有疑问的问题。
当我们看到上面这个图的时候，凭借多年对平面几何的学习，会发现在“三角形ABC”中，满足不了 构成三角形的条件(任意两边之和大于第三边)。 纳尼，那为什么图中能那样子画？
还是“三角形ABC”，以A为起点，B为终点，如果按照平面几何的知识， “两点之间线段最短”， 那么，A到B的最短距离就应该是6(线段AB)，但是，实际上A到B的最短距离却是3+2=5。这又怎么解释？
其实，之所以会有上面的疑问，是因为 对边的权值和边的长度这两个概念的混淆， 。之所以这样画，也只是为了方便理解（每个人写草稿的方式不同，你完全可以用别的方式表示，只要便于你理解即可）。
PS：数组实现邻接表可能较难理解，可以看一下 这里
参考资料：
Dijkstra算法是一种基于贪心策略的算法。每次新扩展一个路程最短的点，更新与其相邻的点的路程。当所有边权都为正时，由于不会存在一个路程更短的没扩展过的点，所以这个点的路程永远不会再被改变，因而保证了算法的正确性。
根据这个原理， 用Dijkstra算法求最短路径的图不能有负权边， 因为扩展到负权边的时候会产生更短的路径，有可能破坏了已经更新的点路径不会发生改变的性质。
那么，有没有可以求带负权边的指定顶点到其余各个顶点的最短路径算法（即“单源最短路径”问题）呢？答案是有的， Bellman-Ford算法 就是一种。（我们已经知道了 Floyd-Warshall 可以解决“多源最短路”问题，也要求图的边权均为正）
通过 邻接矩阵 的Dijkstra时间复杂度是 。其中每次找到离 1 号顶点最近的顶点的时间复杂度是 O(N)，这里我们可以用 优先队列（堆） 来优化，使得这一部分的时间复杂度降低到 。这个我们将在后面讨论。
⑤ 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