登录
2016-04-30 11:32:28

迪杰斯特拉算法 免费编辑 添加义项名

B 添加义项
?
义项指多义词的不同概念,如李娜的义项:网球运动员、歌手等;非诚勿扰的义项:冯小刚执导电影、江苏卫视交友节目等。 查看详细规范>>
所属类别 :
其他数学相关
其他数学相关
编辑分类
Dijkstra算法是典型算法。Dijkstra算法是很有代表性的算法。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。

基本信息

  • 中文名

    迪杰斯特拉算法

  • 外文名

    Dijkstra算法

  • 拼音

    Dí jié sī tè lā suànfǎ

  • Dijkstra算法是

    典型的算法

折叠 编辑本段 基本定义

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。Dijkstra一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 Dijkstra算法运行时迪杰斯特拉算法迪杰斯特拉算法

折叠 编辑本段 相关原理

首先,引进一个辅助向量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程序如下:

// Floyd.cpp : 定义控制台应用程序的入口点。

//

//#include "stdafx.h"

#include<iostream>

#include<vector>

using namespace std;

#define INF 99999 //表示不可到达

#define MAXSIZE 4 //表示图的结点数

//邻接矩阵存储图的信息

/*int map[MAXSIZE][MAXSIZE]={

{0,4,6,6,INF,INF,INF},

{INF,0,1,INF,7,INF,INF},

{INF,INF,0,INF,6,4,INF},

{INF,INF,2,0,INF,5,INF},

{INF,INF,INF,INF,0,INF,6},

{INF,INF,INF,INF,1,0,8},

{INF,INF,INF,INF,INF,INF,0}

};*/

int map[MAXSIZE][MAXSIZE]={

{0,5,INF,7},

{INF,0,4,2},

{3,3,0,2},

{INF,INF,1,0}

};

//弗洛伊德算法

void Floyd()

{

int path[MAXSIZE][MAXSIZE];//保存最短路径

int A[MAXSIZE][MAXSIZE];//a[j]表示当前顶点i到j的最短距离

//数据初始化

for(int i=0;i<MAXSIZE;i++)

{

for(int j=0;j<MAXSIZE;j++)

{

A[j]=map[j];

path[j]=-1;//初始化为-1

}

}

//这个扫描所有点,没有除去对角线和划去的行和列上面的点

/*for(int diagonal=0;diagonal<MAXSIZE;diagonal++)//左对角线

{

for(int k=0;k<MAXSIZE;k++)//行

{

for(int j=0;j<MAXSIZE;j++)//列

{

if(A[k][j]>A[k][diagonal]+A[diagonal][j])

{

A[k][j]=A[k][diagonal]+A[diagonal][j];

path[k][j]=diagonal;

}

}

}

}

*/

for(int diagonal=0;diagonal<MAXSIZE;diagonal++)//左对角线

{

for(int k=0;k<MAXSIZE;k++)//行

{

if(k!=diagonal)//除去此行所有的点

{

for(int j=0;j<MAXSIZE;j++)//列

{

if(j!=diagonal)//除去此列所以的点

{

if(k!=j)//除去对角线的点

{

if(A[k][j]>A[diagonal][j]+A[k][diagonal])//满足条件

{

A[k][j]=A[diagonal][j]+A[k][diagonal];

path[k][j]=diagonal;

}

}

}

}

}

}

}

//结果输出:

for(int i=0;i<MAXSIZE;i++)

{

for(int j=0;j<MAXSIZE;j++)

{

if(A[j]==INF)

cout<<"从顶点"<<i<<"到顶点"<<j<<"不存在路径"<<endl;

else

{

cout<<"从顶点"<<i<<"到顶点"<<j<<"最短距离为: "<<A[j]<<"  其路径为:";

vector<int>temp;

temp.insert(temp.begin(),j);//把终点插入

int ok1=i,ok2=j;

while(true)

{

ok1=path[ok1][ok2];

if(ok1==-1)

break;

temp.insert(temp.begin(),ok1);

}

temp.insert(temp.begin(),i);//把起点插入

for(int z=0;z<temp.size();z++)

cout<<temp[z]<<" ";

cout<<endl;

}

}

}

}

int main()

{

Floyd();

return 0;

}

折叠 编辑本段 描述介绍

在无向图 G=(V,E) 中,假设每条边 E 的长度为 w,找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

折叠 编辑本段 思想内容

按路径长度递增次序产生最短路径算法:

折叠 两组

(1)S:已求出最短路径的顶点的集合(初始时只含有源点V0)

(2)V-S=T:尚未确定最短路径的顶点集合

折叠 加入

保证:

(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为止

算法程序迪杰斯特拉算法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:=qi; d[qi]:=0; } //初始化成true以回避这些点

for i:=1 to n do c:=a[qi,i];

for i:=1 to n-1 do

begin

min:=maxint; //改为最大值

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:=zh;zh:=d[zh];

end;

inc(i);e:=qi; e[0]:=I;

end;

主程序调用:求最短路径长度:初始化t,然后dijkstra(qi,t,c,d)

求路径:make(m,d,e) ,m是终点

迪杰斯特拉算法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取出一个当前累积权值最小,并且没有被处理过的节点[1]

参考资料

阅读全文

热点资讯

我的关注