最短路径分为两类，单元最短路径和多源最短路径。
单源最短路径
给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径 [1] 问题。
无权图的单源最短路径
这里我先说一下我的理解，我们求一个顶点到其它各顶点的最短路径，那么肯定得用bfs算法来遍历。之前的图的遍历和应用中，dfs用了很多，那么现在完全就是类比的概念了，在求两个顶点u，v的路径长度的时候，我们给dfs加了两个形参终点v和长度的d，那么这个bfs的算法也是类是的，不过我们得需要一个数组存储每个顶点到原点的距离，因为是遍历所有的顶点，那么形参v就可以省去了，此时我们需要带一个形参数组进去吗？？其实大可不必，别忘了我们还有visited（标记数组），我们完全可以用它来存储数据，（那么标记的作用岂不是消失了？）并没有，我们初始值，设为一个一看就不是该顶点到初始顶点的距离的数，比如-1，这样当我们存储改顶点到初始顶点的值进去了，直接判断大于0即可，别忘了，我们还需要一个数组来存储路径，（岂不是需要n个数组来记录n个顶点到源点的路径）根本不用，我们只需要一个数组，数组下标对应的每个顶点中存储它上一步的顶点，即是从哪个顶点过来的，这样当我们需要输出从源点到x点的路径的时候，我们只需要输出数组下标x，对应的值就是从某个顶点过来的，如此追踪即可，这是反的路径，我们可以压入栈中，在将其输出。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/* 邻接表存储 - 无权图的单源最短路算法 */ /* dist[]和path[]全部初始化为-1 */ void Unweighted ( LGraph Graph, int dist[], int path[], Vertex S ) { Queue Q; Vertex V; PtrToAdjVNode W; Q = CreateQueue( Graph->Nv ); /* 创建空队列, MaxSize为外部定义的常数 */ dist[S] = 0; /* 初始化源点 */ AddQ (Q, S); while( !IsEmpty(Q) ){ V = DeleteQ(Q); for ( W=Graph->G[V].FirstEdge; W; W=W->Next ) /* 对V的每个邻接点W->AdjV */ if ( dist[W->AdjV]==-1 ) { /* 若W->AdjV未被访问过 */ dist[W->AdjV] = dist[V]+1; /* W->AdjV到S的距离更新 */ path[W->AdjV] = V; /* 将V记录在S到W->AdjV的路径上 */ AddQ(Q, W->AdjV); } } /* while结束*/ } |
有权图的单源最短路径
这个时候就有一个金光闪闪的算法了dijkstra算法
问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
Dijkstra算法的解决方案
Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。
Dijkstra算法的解题思想
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即）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的所有顶点。
问题描述
给定一个带权有向图 G=(V,E) ，其中每条边的权是一个非负实数。另外，还给定 V 中的一个顶点，称为源。现在我们要计算从源到所有其他各顶点的最短路径长度。这里的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。
Dijkstra算法的解决方案
Dijkstra提出按各顶点与源点v间的路径长度的递增次序，生成到各顶点的最短路径的算法。既先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从源点v 到其它各顶点的最短路径全部求出为止。
Dijkstra算法的解题思想
将图G中所有的顶点V分成两个顶点集合S和T。以v为源点已经确定了最短路径的终点并入S集合中，S初始时只含顶点v,T则是尚未确定到源点v最短路径的顶点集合。然后每次从T集合中选择S集合点中到T路径最短的那个点，并加入到集合S中，并把这个点从集合T删除。直到T集合为空为止。
具体步骤
1、选一顶点v为源点，并视从源点v出发的所有边为到各顶点的最短路径（确定数据结构：因为求的是最短路径，所以①就要用一个记录从源点v到其它各顶点的路径长度数组dist[],开始时，dist是源点v到顶点i的直接边长度，即dist中记录的是邻接阵的第v行。②设一个用来记录从源点到其它顶点的路径数组path[],path中存放路径上第i个顶点的前驱顶点）。
2、在上述的最短路径dist[]中选一条最短的，并将其终点（即
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的所有顶点。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
/* 邻接矩阵存储 - 有权图的单源最短路算法 */ Vertex FindMinDist( MGraph Graph, int dist[], int collected[] ) { /* 返回未被收录顶点中dist最小者 */ Vertex MinV, V; int MinDist = INFINITY; for (V=0; V<Graph->Nv; V++) { if ( collected[V]==false && dist[V]<MinDist) { /* 若V未被收录，且dist[V]更小 */ MinDist = dist[V]; /* 更新最小距离 */ MinV = V; /* 更新对应顶点 */ } } if (MinDist < INFINITY) /* 若找到最小dist */ return MinV; /* 返回对应的顶点下标 */ else return ERROR; /* 若这样的顶点不存在，返回错误标记 */ } bool Dijkstra( MGraph Graph, int dist[], int path[], Vertex S ) { int collected[MaxVertexNum]; Vertex V, W; /* 初始化：此处默认邻接矩阵中不存在的边用INFINITY表示 */ for ( V=0; V<Graph->Nv; V++ ) { dist[V] = Graph->G[S][V]; if ( dist[V]<INFINITY ) path[V] = S; else path[V] = -1; collected[V] = false; } /* 先将起点收入集合 */ dist[S] = 0; collected[S] = true; while (1) { /* V = 未被收录顶点中dist最小者 */ V = FindMinDist( Graph, dist, collected ); if ( V==ERROR ) /* 若这样的V不存在 */ break; /* 算法结束 */ collected[V] = true; /* 收录V */ for( W=0; W<Graph->Nv; W++ ) /* 对图中的每个顶点W */ /* 若W是V的邻接点并且未被收录 */ if ( collected[W]==false && Graph->G[V][W]<INFINITY ) { if ( Graph->G[V][W]<0 ) /* 若有负边 */ return false; /* 不能正确解决，返回错误标记 */ /* 若收录V使得dist[W]变小 */ if ( dist[V]+Graph->G[V][W] < dist[W] ) { dist[W] = dist[V]+Graph->G[V][W]; /* 更新dist[W] */ path[W] = V; /* 更新S到W的路径 */ } } } /* while结束*/ return true; /* 算法执行完毕，返回正确标记 */ } |
多元最短路径
floyd算法
太难了，学了好半天，这个算法实在是不想看了，，
核心思路编辑
路径矩阵
通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。 [3]
从图的带权邻接矩阵A=[a(i,j)] n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);
状态转移方程
其状态转移方程如下： map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}；
map[i,j]表示i到j的最短距离，K是穷举i,j的断点，map[n,n]初值应该为0，或者按照题目意思来做。
当然，如果这条路没有通的话，还必须特殊处理，比如没有map[i,k]这条路。
算法过程编辑
1，从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。
2，对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。
把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G[i][j]=d，d表示该路的长度；否则G[i][j]=无穷大。定义一个矩阵D用来记录所插入点的信息，D[i][j]表示从Vi到Vj需要经过的点，初始化D[i][j]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G[i][j] = min( G[i][j], G[i][k]+G[k][j] )，如果G[i][j]的值变小，则D[i][j]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。
比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。 [4]
时间复杂度与空间复杂度编辑
时间复杂度:O(n^3)；
空间复杂度:O(n^2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
* 邻接矩阵存储 - 多源最短路算法 */ bool Floyd( MGraph Graph, WeightType D[][MaxVertexNum], Vertex path[][MaxVertexNum] ) { Vertex i, j, k; /* 初始化 */ for ( i=0; i<Graph->Nv; i++ ) for( j=0; j<Graph->Nv; j++ ) { D[i][j] = Graph->G[i][j]; path[i][j] = -1; } for( k=0; k<Graph->Nv; k++ ) for( i=0; i<Graph->Nv; i++ ) for( j=0; j<Graph->Nv; j++ ) if( D[i][k] + D[k][j] < D[i][j] ) { D[i][j] = D[i][k] + D[k][j]; if ( i==j && D[i][j]<0 ) /* 若发现负值圈 */ return false; /* 不能正确解决，返回错误标记 */ path[i][j] = k; } return true; /* 算法执行完毕，返回正确标记 */ } |
