单源最短路径
单源最短路径问题
问题描述
给定一个带权有向图 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]与dist[j]的较小者
4、再选出一个到源点v路径长度最小的顶点k,从T中删去后加入S中，再回去到第三步，如此重复，直到集合S中的包含图G的所有顶点
Program Dijkstra;
Const
MaxP=5;
Infinity =MaxLongInt;
M = MaxLongInt;
map : Array [1..5,1..5] Of LongInt =
((M ,10 ,M ,30 ,100),
(M ,M ,50 ,M ,M ),
(M ,M ,M ,M ,10 ),
(M ,M ,20 ,M ,60 ),
(M ,M ,M ,M ,M ));
Var
{ map : Array [1..MaxP, 1..MaxP] Of LongInt;}
{ 邻接矩阵, Infinity表示没有边相连 }
path : Array [1..MaxP] Of LongInt;
{ 路径数组, 记录从源点出发的具体最短路径 }
source : LongInt;
{ 源点变量 }
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 (NOT Visited[j]) AND (dist[j]<min) Then
Begin
min:=dist[j]; minp:=j;
End;
{ 已找到源点到点minp的最短路径, 做上标志 }
Visited[minp]:=True;
{ 修改距离数组 }
For j:=1 To MaxP Do
If (NOT Visited[j]) AND (dist[minp]+map[minp,j]<dist[j]) Then
Begin
dist[j]:=dist[minp]+map[minp,j]; path[j]:=minp;
End;
End;
End;