单源最短路径Dijkstra算法的实现.docx

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){ //这里的s是指计算最小路径的源,但是题目中没有
用到,应该加一个
//初始化数组D的函数
/*
for(int i =0; i<G->n() ; i++){//仅供参考(本来这个初始化应该在传入时候就做好的,但是为了符合这个函数)
if(i ==s ) D[i] =0;
else D[i]=INFINITY;
}
*/
int i,v,w;
for(i=0;i<G->n();i++)