迪克斯特拉算法

電子系2000級(jí)

數(shù)據(jù)結(jié)構(gòu)

DataStructure

WithCorC++

編輯課件最短路徑兩點(diǎn)間邊數(shù)最少的路徑可用作交通自動(dòng)咨詢系統(tǒng)兩點(diǎn)間邊權(quán)重的和最小的路徑用來(lái)計(jì)算兩城市間路程最短，時(shí)間最快，費(fèi)用最省的路徑

編輯課件兩點(diǎn)A,B之間邊數(shù)最少的路徑

從A點(diǎn)出發(fā)，對(duì)圖做廣度優(yōu)先遍歷。從根A到B的路徑就是邊數(shù)最少的路徑，也就是中轉(zhuǎn)次數(shù)最少的路徑。編輯課件單源點(diǎn)到其余各點(diǎn)權(quán)重和最小的路徑從v0到其余各點(diǎn)的最短路徑v3v0v5v2v450v153060100201010起點(diǎn)終點(diǎn)最短路徑長(zhǎng)度v0v1

v2

v3

v4

v5

(v0,v4)30(v0,v2)10(v0,v4,v3)50(v0,v4,v3,v5)60編輯課件迪克斯特拉Dijkstra算法按路徑長(zhǎng)度遞增逐步產(chǎn)生最短路徑設(shè)集合S存放已經(jīng)求出的最短路徑的終點(diǎn)，開(kāi)始，S中只有一個(gè)源點(diǎn)v0，以后每求得的一條最短路徑就將終點(diǎn)參加S，直到全部頂點(diǎn)都參加到S.定義一個(gè)數(shù)組D[n];n是圖的頂點(diǎn)數(shù)。D[i]=從源點(diǎn)v0到頂點(diǎn)vi最短路經(jīng)的長(zhǎng)度。第一步取D[i]為v0到vi的邊的權(quán)值，無(wú)邊時(shí)取值∞，取一個(gè)最小值D[j1]=min{D[i],i<n}D[j1]是v0到vj1的最短路徑的長(zhǎng)度。編輯課件第一步v3v0v5v2v450v1530601001010123456D[i]

1030100j1=2D[2]=10是v0到v2的最短路徑的長(zhǎng)度20L={v0}L={v0,v2}編輯課件迪克斯特拉Dijkstra算法已經(jīng)有L={v0,v2}，下一條最短路徑(終點(diǎn)vj2),或者是(v0vj2),或者是(v0,vj1,vj2)。

對(duì)每個(gè)頂點(diǎn)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的最短路徑的長(zhǎng)度。

編輯課件第二步v3v0v5v2v450v1530601001010123456

jD[I]

1030100

2D[i]

60

4j2=4D[4]=30是v0到v4的最短路徑的長(zhǎng)度20L={v0,v2}L={v0,v2,v4}編輯課件遞歸過(guò)程：重復(fù)第二步設(shè)已經(jīng)有v0到vj1,vj2···,vjk的最短路徑對(duì)每個(gè)頂點(diǎn)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的最短路徑的長(zhǎng).編輯課件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}時(shí)間復(fù)雜性O(shè)(n2)編輯課件

令L={vj1,vj2···,vjk-1}是已經(jīng)求得的從v0出發(fā)的最短路徑的終點(diǎn)的集合，可以證明下一條最短路徑(終點(diǎn)vjk),是只通過(guò)S中頂點(diǎn)到達(dá)vjk的。否那么設(shè)v0到vjk的路徑中有一個(gè)不在S中出現(xiàn)的頂點(diǎn)vp，但是路徑v0···vp···vjk比v0···vp長(zhǎng)應(yīng)領(lǐng)先有v0···vp的最短路徑，以歸納假設(shè)vp應(yīng)當(dāng)已經(jīng)出現(xiàn)于L中。

編輯課件template<classT>

structPathInfo

{

T

startV,endV;

intcost;

};

template<classT>

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

{

returna.cost<=b.cost;

}

編輯課件//用優(yōu)先序列實(shí)現(xiàn)最短路徑算法

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*D=newint[n];

int**P=new(int**[n])[n];

ShortestPathDijkstra(G,0,D,P);

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

{cout<<"P["<<i<<"]={";

cout<<P[i][0];

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

cout<<","<<P[i][j];

cout<<"}"<<endl;

}

}編輯課件每一對(duì)頂點(diǎn)之間的最短路徑可讓每個(gè)頂點(diǎn)作起始點(diǎn)以用Dijkstra算法算一遍，共n遍，時(shí)間復(fù)雜性O(shè)(n3).弗洛伊德Floyd算法更直接編輯課件弗洛伊德Floyd算法定義Dk(u,v)為從u到v的長(zhǎng)度最短的k-path.假設(shè)從u到v的最短(k-1)-path，那么最短k-path要么經(jīng)過(guò)，要么不經(jīng)過(guò)頂點(diǎn)k。如果經(jīng)過(guò)頂點(diǎn)k,那么最短k-path是從u到k的最短(k-1)-path,再連接從k到v的最短(k-1)-path。如果不經(jīng)過(guò)頂點(diǎn)k，那么最短路徑保持k-1-path不變。編輯課件v0v23v124611

DD-1D0D1

D2012012012012004110411046046160260260250223∞0370370370PP-1P0P1P20120120120120v0v1v0v2v0v1v0v2v0v1v0v1v2v0v1v0v1v21v1v0v1v2v1v0v1v2v1v0v1v2v1v2v0v1v22v2v0v2v0v2v0v1v2v0v2v0v1v2v0v2v0v1編輯課件弗洛伊德Floyd算法int**D=new(int**[n])[n];int***P=new((int***[n])[n])[n];D-1[i][j]=arc[i][j];Dk[i][j]=min{Dk-1[i][j],Dk-1[i][k]+Dk-1[k][j]}編輯課件#include"graph.h"

#defineMaxInt32767

typedefint**DistanceMatrix;

typedefint**PathMatrix;

編輯課件template<classT>

voidShortestPathFloyd(Graph<T>G,PathMatrix*&P,

DistanceMatrix&D)

{intn=G.NumberOfVertices();

inti,j,k,l,t;T

u,v,w;

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

{u=GetVertex(G,i);

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

{v=GetVertex(G,j);

D[i][j]=MaxInt;

l=G.GetWeight(u,v);

if(l>0)D[i][j]=l;

for(k=0;k<n;k+