问题描述

解决方案

问题的提出

解题思想

参考程序(pascal Dijkstra算法的实现（c++）)

问题描述

给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。

解决方案

Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。

问题的提出

给定一个带权有向图G与源点v，求从v到G中其它顶点的最短路径。限定各边上的权值大于或等于0。

解题思想

将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。

具体步骤

1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。

2、在上述的最短路径dist[]中选一条最短的，并将其终点（即<v,k>）k加入到集合s中。

3、调整T中各顶点到源点v的最短路径。 因为当顶点k加入到集合s中后，源点v到T中剩余的其它顶点j就又增加了经过顶点k到达j的路径,这条路径可能要比源点v到j原来的最短的还要短。调整方法是比较dist[k]+g[k,j]与dist[j]，取其中的较小者。

4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点。

参考程序

pascal

PROCEDURE DIJKSTRA;

VAR

DIST:ARRAY[1..MAXP]OF LONGINT;{距离数组,记录目前从源点出发已经找到的最短路径长度}

VISITED:ARRAY[1..MAXP]OF BOOLEAN;{标志数组,记录是否已经找到了某一点的最终最短路径}

I,J,MIN,MINP:LONGINT;

BEGIN

FILLCHAR(VISITED,SIZEOF(VISITED),FALSE);{初始化源点和路径数组}

FOR I:=1 TO MAXP DO

BEGIN

DIST:=MAP[SOURCE,I];

IF DIST<M THEN

PATH:=SOURCE

ELSE

PATH:=0;

END;{源点的最短路径肯定是不用找的...}

VISITED[SOURCE]:=TRUE;

{DIJKSTRA的思想是按递增长度来产生路径,每次选出当前已经

找到的最短的一条路径,它必然是一条最终的最短路径.因此

每次找出当前距离数组中最小的,必然是一条最终的最短路径}

FOR I:=2 TO MAXP DO

BEGIN

MIN:=INFINITY;

MINP:=0;

FOR J:=1 TO MAXP DO

IF (NOTVISITED[J]) AND (DIST[J]<MIN) THEN

BEGIN

MIN:=DIST[J];

MINP:=J;

END;{已找到源点到点MINP的最短路径,做上标志}

VISITED[MINP]:=TRUE;{修改距离数组}

FOR J:=1 TO MAXP DO

IF (NOTVISITED[J]) AND (DIST[MINP]+MAP[MINP,J]<DIST[J]) THEN

BEGIN

DIST[J]:=DIST[MINP]+MAP[MINP,J];

PATH[J]:=MINP;

END;

END;

END;

Dijkstra算法的实现（c++）

//Compute shortest path distances from s,return them in D

void Dijkstra(Graph *G,int *D,int s){

int i,v,w;

for(i=0;i<G->n();i++){ //Process the vertices

v=minVertex(G,D);

if(D[v]==INFINITY) return; //Unreachable vertices

G->setMark(v,VISITED);

for(w=G->first(v);w<G->n();w=G->nexr(v,w))

if(D[w]>(D[v]+G->weight(v,w)))

D[w]=D[v]+G->weight(v,w);

}

}