迪杰斯特拉算法_在线百科全书查询
迪杰斯特拉算法
定义及问题描述
定义
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 最短路
