迪克斯特拉算法

电子系2000级

数据结构

DataStructure

WithCorC++

最短路径两点间边数最少的路径可用作交通自动咨询系统两点间边权重的和最小的路径用来计算两城市间路程最短，时间最快，费用最省的路径

两点A,B之间边数最少的路径

从A点出发，对图做广度优先遍历。从根A到B的路径就是边数最少的路径，也就是中转次数最少的路径。单源点到其余各点权重和最小的路径从v0到其余各点的最短路径v3v0v5v2v450v153060100201010起点终点最短路径长度v0v1

v2

v3

v4

v5

(v0,v4)30(v0,v2)10(v0,v4,v3)50(v0,v4,v3,v5)60迪克斯特拉Dijkstra算法按路径长度递增逐步产生最短路径设集合S存放已经求出的最短路径的终点，开始，S中只有一个源点v0，以后每求得的一条最短路径就将终点加入S，直到全部顶点都加入到S.定义一个数组D[n];n是图的顶点数。D[i]=从源点v0到顶点vi最短路经的长度。第一步取D[i]为v0到vi的边的权值，无边时取值∞，取一个最小值D[j1]=min{D[i],i<n}

D[j1]是v0到vj1的最短路径的长度。第一步v3v0v5v2v450v1530601001010123456D[i]

1030100j1=2D[2]=10是v0到v2的最短路径的长度20L={v0}L={v0,v2}迪克斯特拉Dijkstra算法已经有L={v0,v2}，下一条最短路径(终点vj2),或者是(v0vj2),或者是(v0,vj1,vj2)。

对每个顶点vi,比较D[i]与D[j1]+arc[j1][i],取其小更新D[i]=min{D[i],D[j1]+arc[j1][i]}

取D[j2]=min{D[i],i<n,i≠j1}则D[j2]是v0到vj2的最短路径的长度。

第二步v3v0v5v2v450v1530601001010123456

jD[I]

1030100

2D[i]

60

4j2=4D[4]=30是v0到v4的最短路径的长度20L={v0,v2}L={v0,v2,v4}递归过程：重复第二步设已经有v0到vj1,vj2···,vjk的最短路径对每个顶点vi,vi≠vj1,vj2···,vjk,更新

D[i]=min{D[i],D[jk]+arc[jk][i]}令

D[jk+1]=min{D[i],i<n,i≠j1,j2···,jk}则

D[jk+1]是v0到vjk+1的最短路径的长.v3v0v5v2v450v153060100101012345

LD[i]010(v0,v2)30(v0,v4)100(v0,v5)2D[i]

060(v0,v2,v3)4D[i]50(v0,v4,v3)090(v0,v4,v5)3D[i]060(v0,v4,v3,v5)520迪克斯特拉

Dijkstra算法L={v0,v2,v4,v3,v5}时间复杂性O(n2)

令L={vj1,vj2···,vjk-1}是已经求得的从v0出发的最短路径的终点的集合，可以证明下一条最短路径(终点vjk),是只通过S中顶点到达vjk的。否则设v0到vjk的路径中有一个不在S中出现的顶点vp，但是路径v0···vp···vjk比v0···vp长应当先有v0···vp的最短路径，以归纳假设vp应当已经出现于L中。

template<classT>

structPathInfo

{

T

startV,endV;

intcost;

};

template<classT>

intoperator<=(constPathInfo<T>&a,constPathInfo<T>&b)

{

returna.cost<=b.cost;

}

//用优先序列实现最短路径算法

template<classT>

intGraph<T>::MinimumPath(constT&sVertex,

constT&eVertex)

{PQueue<PathInfo<T>>PQ(MaxGraphSize);

PathInfo<T>pathData;

SeqList<T>L,adjL;

SeqListIterator<T>adjLiter(adjL);

T

sv,ev;

intmincost;

pathData.startV=sVertex;

pathData.endV=sVertex;

pathData.cost=0;

PQ.PQInsert(pathData);

while(!PQ.PQEmpty())

{pathData=PQ.PQDelete();

ev=pathData.endV;

mincost=pathData.cost;

if(ev==eVertex)break;

if(!FindVertex(L,ev))

{L.Insert(ev);sv=ev;

adjL=GetNeighbors(sv);

adjLiter.SetList(adjL);

for(adjLiter.Reset();!adjLiter.EndOfList();adjLiter.Next())

{ev=adjLiter.Data();

if(!FindVertex(L,ev))

{pathData.startV=sv;

pathData.endV=ev;

pathData.cost=mincost+GetWeight(sv,ev);

PQ.PQInsert(pathData);

}}}}

if(ev==eVertex)

returnmincost;

else

return-1;

}template<classT>

TGetVertex(Graph<T>G,intpos)

{inti,n=G.NumberOfVertices();

if(pos<0||pos>=n)

{cerr<<"Therearenotsomanyvertices!";

return0;}

VertexIterator<T>liter(G);

i=0;

while(!liter.EndOfList()&&i!=pos)

{i++;

liter.Next();}

returnliter.Data();

}template<classT>

voidShortestPathDijkstra(Graph<T>G,intv0,int*D,int**P)

{inti,j,k,l,min,n=G.NumberOfVertices();

T

u,v,w;

u=GetVertex(G,v0);

int*final=newint[n];

for(i=0;i<n;i++)

{final[i]=0;

v=GetVertex(G,i);

for(j=0;j<n;j++)P[i][j]=0;//initialP[i][j]

D[i]=G.GetWeight(u,v);//initialD[i]

if(D[i]<MaxInt){P[i][v0]=1;P[i][i]=1;}

//p[i][j]=1iffvertexjisinthepathfromv0toi

}

D[v0]=0;final[v0]=1;

for(i=1;i<n;i++)

{min=MaxInt;

for(j=1;j<n;j++)//GettheminimumD[k]

if(final[j]==0)//vertexjhasnotmarked.

if(D[j]<min)

{k=j;min=D[j];}

final[k]=1;//markedvertexk,

v=GetVertex(G,k);//foundtheshortestpath

for(j=1;j<n;j++)

{w=GetVertex(G,j);l=G.GetWeight(v,w)+min;

if(!final[j]&&(l<D[w]))

{D[w]=l;//renewD[w]

P[j]=P[k];P[j][j]=1;}}}}

voidmain()

{Graph<char>G;

G.ReadGraph("sctest.dat");

intn=G.NumberOfVertices();

int