floyd算法、Dijkstra算法实例讲解
- 格式：doc
- 大小：157.00 KB
- 文档页数：7
下载文档原格式
合集下载
两点之间最短路径算法
两点之间最短路径的算法有三种：Dijkstra算法、Floyd-Warshall 算法、Bellman-Ford算法。
1. Dijkstra算法：该算法使用贪心策略，每次选择距离起点最近的节点进行扩展，直到到达终点。
它适用于有向图和无向图，但不适用于存在负权边的图。
2. Floyd-Warshall算法：该算法使用动态规划策略，通过计算每个节点到其他所有节点的距离，来寻找最短路径。
它适用于有向图和无向图，也可以处理负权边，但不适用于存在负权环的图。
3. Bellman-Ford算法：该算法结合了Dijkstra 算法和Floyd-Warshall 算法的优点，可以在存在负权边的图中寻找最短路径，同时可以检测出是否存在负权环。
具体选择哪种算法，要根据实际情况和需求来确定。
最短路径算法(dijkstra)经典例题
最短路径算法(dijkstra)经典例题
以下是一个经典的最短路径算法(dijkstra)的例题：
假设有一张地图，如下所示：
```
A--2--B
| |
4 3
| |
C--5--D
```
其中，A、B、C、D代表地点，数字代表两个地点之间的距离。
从A出发，要求找到到达D的最短路径。
首先，我们需要初始化节点的距离。
假设A节点的距离初始
为0，其他节点的距离初始为无穷大。
1. 选择起始节点A，并将其距离设为0。
2. 从A开始，计算A的邻居节点的距离。
B距离为2，C距离
为4。
3. 选择距离最小的节点，即B。
将B的距离设为已知最小距离，并标记为已访问。
4. 计算B的邻居节点C和D的距离。
C距离为6，D距离为5。
5. 选择距离最小的节点，即D。
将D的距离设为已知最小距离，并标记为已访问。
6. 计算D的邻居节点C的距离。
C距离为7。
7. 选择距离最小的节点，即C。
将C的距离设为已知最小距离，并标记为已访问。
8. 计算C的邻居节点B和D的距离。
B距离为9，D距离为12。
9. 选择距离最小的节点，即B。
将B的距离设为已知最小距离，并标记为已访问。
10. 到达目标节点D，找到最短路径。
最终的最短路径为A -> B -> D，距离为2 + 3 = 5。
在实际应用中，为了更高效地计算最短路径，可以使用优先队列或者最小堆来实现节点的选择过程。
求网络间两点的距离
一、 最短路径最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。
在求解网络图上节点间最短路径的方法中，用于解决最短路径问题的算法被称作“最短路径算法”。
最常用的路径算法有：Dijkstra 算法，A*算法，SPFA 算法，Bellman-Ford 算法，Floyd-Warshall 算法，Johnson 算法等。
迪克斯特拉(Dijkstra)及弗罗伊德(Floyd)算法是其中应用较广的算法。
这两种算法中,网络被抽象为一个图论中定义的有向或无向图，并利用图的节点邻接矩阵记录点间的关联信息。
在进行图的遍历以搜索最短路径时，以该矩阵为基础不断进行目标值的最小性判别,直到获得最后的优化路径。
下面将对这两种算法进行阐述。
二、Dijkstra 算法、Floyd 算法基本步骤：Dijkstra(迪杰斯特拉 )算法是典型的最短路径路由算法 ，用于计算一个节点到其他所有节点的最短路径。
主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
Dijkstra 算法 能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
（一）Dijkstra 算法：令：{}{}_23,1,,,,i n s v i s v v v ===并令：{()()10,j j W v T v v s-==∞∈1、 对j v s -∈，求()(){}()min ,j i ij j T v W v w T v +=。
2、 求(){}min j jv sT v ∈得()kT v ，使()kT v =(){}min j jv sT v ∈令()()k k W v T v =3、若k n v v =则已找到1v 到n v 的最短路距离()k W v ，否则令i k =从s -中删去i v 转1这样经过有限次迭代则可以求出1v 到n v 的最短路线，可以用一个流程图来表示：第一步 先取()10W v =意即1v 到1v 的距离为0,而()j T v 是对()j T v 所赋的初值。
Floyd算法
Floyd算法Floyd算法是一种经典的图论算法，用于求解带权有向图中任意两个顶点之间的最短路径问题。
该算法由美国数学家罗伯特·弗洛伊德（Robert Floyd）于1962年提出，因此得名为Floyd算法。
Floyd算法是一种动态规划算法，它采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决子问题，最终得到解决整个问题的结果。
本文将从算法的背景、基本思想、实现方法及优缺点等方面对Floyd 算法进行详细阐述和分析。
一、算法的背景在讲Floyd算法之前，我们先来了解一下最短路径问题。
顾名思义，最短路径问题就是在给定图中找到两个给定节点之间的一条最短路径，也就是路径上各边权值之和最小的路径。
这个问题在现实生活中有很多应用，比如网络路由、地图路径规划、航线安排等等。
在数学和计算机科学领域中，我们可以通过图论的方法来描述和解决这个问题。
一般来说，给定一张带权有向图G=(V, E)，其中V表示节点的集合，E表示边的集合。
每条边E(i,j)的权重为w(i,j)，表示从节点i到节点j的距离或成本。
那么最短路径问题就是在图中找到从节点s到节点t的一条最短路径P，并且P上的边权之和最小。
最初求解的思路是按照类似深度优先搜索的方式，逐个遍历所有路径，然后依次比较它们的距离，找到最短路径。
但这种方式显然是不可行的，因为它的时间复杂度非常高。
所以，我们需要设计一种更高效的算法，以求得最短路径问题的最优解。
二、算法的基本思想Floyd算法就是一种高效地解决最短路径问题的方法。
它采用了“动态规划”的思想，通过逐步求解子问题，最终得到完整的最短路径。
而解决子问题的方式则是采用了“分治”的思想，将问题分解为更小的子问题，然后逐步解决。
具体地说，Floyd算法采用了“中转节点”的概念，我们可以将问题转化为这样一个子问题：对于每个节点i和节点j，假设我们已经知道了它们之间的最短路径长度为d[i][j]，那么考虑一下节点k作为中转节点，它可以为i和j之间的路径P提供一个“中转服务”，将P拆分为两条路径：i-->k和k-->j。
五大最短路径算法比较
五大最短路径算法比较五大最短路径算法是指迪杰斯特拉算法（Dijkstra's algorithm）、贝尔曼-福德算法（Bellman-Ford algorithm）、弗洛伊德算法（Floyd-Warshall algorithm）、A*算法和迭代加深算法（Iterative Deepening Search algorithm）。
这五个算法在计算最短路径时有不同的特点和优劣，下面将对它们进行详细比较。
首先是迪杰斯特拉算法，它是一种单源最短路径算法，用于计算其中一个顶点到其他所有顶点的最短路径。
该算法适用于有向图和带非负权值边的图，时间复杂度为O(V^2)，其中V是顶点数。
迪杰斯特拉算法通过维护一个距离数组来记录每个顶点到起点的最短路径长度，然后通过松弛操作不断更新最短路径，直到找到到达目标顶点的最短路径。
迪杰斯特拉算法的优点是简单易懂，可以得到正确的解，并且在稠密图中有较好的表现；然而，它的缺点是无法处理带负权边的图和带有负循环的图。
其次是贝尔曼-福德算法，它是一种多源最短路径算法，用于计算任意两个顶点之间的最短路径。
该算法适用于有向图和带任意权值边的图，时间复杂度为O(VE)，其中V是顶点数，E是边数。
贝尔曼-福德算法通过对所有边进行松弛操作来不断更新最短路径，直到没有可以更新的路径为止。
贝尔曼-福德算法的优点是可以处理带负权边的图和带有负循环的图，并且能够检测出负权环；然而，它的缺点是时间复杂度较高，不适用于大规模图的计算。
第三个是弗洛伊德算法，它是一种多源最短路径算法，用于计算任意两个顶点之间的最短路径。
该算法适用于带有任意权值边的图，时间复杂度为O(V^3)，其中V是顶点数。
弗洛伊德算法通过维护一个邻接矩阵来记录每对顶点之间的最短路径长度，然后通过动态规划的方法不断更新最短路径，直到找到所有最短路径。
弗洛伊德算法的优点是可以处理带负权边的图和带有负循环的图，并且能够找到所有最短路径；然而，它的缺点是时间复杂度较高，不适用于大规模图的计算。
dijkstra算法
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。
是从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
定义Dijkstra算法一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表的方式，这里均采用永久和临时标号的方式。
注意该算法要求图中不存在负权边。
迪克斯特拉算法原理1.首先，引入一个辅助数组(vector)D，它的每个元素D表示当前所找到的Dijkstra算法运行动画过程从起始点（即源点）到其它每个顶点的长度。
例如，D[3] = 2表示从起始点到顶点3的路径相对最小长度为2。
[1] 这里强调相对就是说在算法执行过程中D的值是在不断逼近最终结果但在过程中不一定就等于长度。
[3]2.D的初始状态为：若从到有弧（即从到存在连接边），则D为弧上的权值（即为从到的边的权值）；否则置D为∞。
显然，长度为D = Min{ D | ∈V } 的路径就是从出发到顶点的长度最短的一条路径，此路径为()。
3.那么，下一条长度次短的是哪一条呢？也就是找到从源点到下一个顶点的最短路径长度所对应的顶点，且这条最短路径长度仅次于从源点到顶点的最短路径长度。
假设该次短路径的终点是，则可想而知，这条路径要么是()，或者是()。
它的长度或者是从到的弧上的权值，或者是D加上从到的弧上的权值。
4.一般情况下，假设S为已求得的从源点出发的最短路径长度的顶点的集合，则可证明：下一条次最短路径（设其终点为）要么是弧()，或者是从源点出发的中间只经过S中的顶点而最后到达顶点的路径。
因此，下一条长度次短的的最短路径长度必是D = Min{ D | ∈V-S }，其中D要么是弧()上的权值，要么是D(，∈S)和弧(，)上的权值之和。
弗洛伊德（Floyd）算法
弗洛伊德（Floyd）算法最短路径问题：从某个顶点出发到达另外⼀个顶点的所经过的边的权重和最⼩的⼀条路径弗洛伊德算法解决最短路径问题1.基本思想（1）计算图中各个顶点之间的最短路径，每⼀个顶点都是出发访问点，所以需要将每⼀个顶点看做被访问顶点，求出从每⼀个顶点到其他顶点的最短路径（2）所有顶点都作为中间节点遍历⼀次，每次遍历将各个顶点经过中间节点到另⼀个节点的距离，与不经过该节点的距离相⽐较，若经过中间节点的距离更⼩，就更新距离表与前驱关系（3）时间复杂度O(n3)，所有顶点作为出发点、中间节点、终点，每个顶点都要遍历3次2.步骤（1）设置顶点 a 到顶点 b 的最短路径已知为 L ab，顶点 b 到 c 的最短路径已知为 L bc，顶点 a 到 c 的路径为 L ac，则 a 到 c 的最短路径为：min ( ( L ab + L bc ), L ac )，b 的取值为图中所有顶点，则可获得 a 到 b 的最短路径（2）⾄于 a 到 b 的最短路径 L ab或者 b 到 c 的最短路径 L bc，是以同样的⽅式获得（3）三个点为同⼀顶点时：中间顶点为⾃⾝；三个点是不同顶点时：中间顶点是终点的前驱节点；两个顶点直接连通时：中间节点为出发点代码实现import java.util.Arrays;public class Floyd {//弗洛伊德算法解决最短路径问题public static final int BLOCK = 65535;//表⽰顶点之间不直接连通public static void main(String[] args) {char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};//顶点到⾃⾝距离为0int[][] matrix = {{0, 5, 7, BLOCK, BLOCK, BLOCK, 2},{5, 0, BLOCK, 9, BLOCK, BLOCK, 3},{7, BLOCK, 0, BLOCK, 8, BLOCK, BLOCK},{BLOCK, 9, BLOCK, 0, BLOCK, 4, BLOCK},{BLOCK, BLOCK, 8, BLOCK, 0, 5, 4},{BLOCK, BLOCK, BLOCK, 4, 5, 0, 6},{2, 3, BLOCK, BLOCK, 4, 6, 0}};Graph graph = new Graph(matrix, vertex);graph.floyd();graph.result();}}//带权⽆向图class Graph {public char[] vertex;//存放顶点public int[][] matrix;//保存各个顶点到其它顶点的距离，初始为直接连接的距离，算法计算后为最短距离public int[][] relay;//保存中间结点//构造器public Graph(int[][] matrix, char[] vertex) {this.vertex = vertex;this.matrix = matrix;this.relay = new int[vertex.length][vertex.length];//三个点为同⼀顶点时：中间顶点为⾃⾝；三个点是不同顶点时：中间顶点是终点的前驱节点；两个顶点直接连通时：中间节点为出发点for (int i = 0; i < vertex.length; i++) {Arrays.fill(relay[i], i);//初始中间顶点为⾃⾝}}//显⽰算法结果public void result() {for (int k = 0; k < vertex.length; k++) {for (int i = 0; i < vertex.length; i++) {System.out.println(vertex[k] + " 到 " + vertex[i] +" 最短路径 " + matrix[k][i] +" 中间结点 " + vertex[relay[k][i]]);}System.out.println();}}//弗洛伊德算法public void floyd() {int temp;//保存i到j的距离for (int i = 0; i < matrix.length; i++) {//出发点ifor (int j = 0; j < matrix.length; j++) {//中间顶点jfor (int k = 0; k < matrix.length; k++) {//终点ktemp = matrix[i][j] + matrix[j][k];//求从i出发，经过k，到达j的距离 if (temp < matrix[i][k]) {matrix[i][k] = temp;//更新距离relay[i][k] = relay[j][k];//更新中间顶点}}}}}}。
Floyd算法详解
Floyd算法详解Floyd-WarshallFloyd算法，是⼀种著名的多源最短路算法。
核⼼思想：⽤邻接矩阵存储图，核⼼代码为三重循环，第⼀层枚举中间点k，⼆三层分别枚举起始点i与⽬标点j。
然后判断经过中间点k后，i与j间的路程是否会减⼩。
如果是，就更新i，j之间的最短路。
for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(e[i][j]>e[i][k]+e[k][j])e[i][j]=e[i][k]+e[k][j];需要注意的是，为了保证更新成功，需要将e数组初始化为⽆穷⼤。
同时为了防⽌程序做⽆意义的到⾃⼰的最短路，将每个节点到本⾝的距离初始化为0。
算法复杂度：该算法的空间复杂度为n^2(不算优秀，但勉强接受),时间复杂度O(n^3)（呵呵）。
完整代码：#include<iostream>#include<cstring>#include<cstdio>using namespace std;const int inf=99999999;int n,m,x,y,z,s;int dis[1001][1001];int main(){scanf("%d%d%d",&n,&m,&s);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i!=j) dis[i][j]=inf;else dis[i][j]=0;for(int i=1;i<=m;i++){scanf("%d%d%d",&x,&y,&z);dis[x][y]=dis[y][x]=z;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(dis[i][k]+dis[k][j]<dis[i][j])dis[i][j]=dis[i][k]+dis[k][j];for(int i=1;i<=n;i++)printf("%d ",dis[s][i]);return0;}算法优化：for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]),dis[j][i] = dis[i][j];这⾥利⽤了矩阵的对称性，只更新⼀半矩阵即可。
交通路网优化中的路径规划算法综述
交通路网优化中的路径规划算法综述交通拥堵是大城市面临的一个重要挑战。
为了缓解交通拥堵问题，提高交通效率，路径规划算法在交通路网优化中起着重要的作用。
本文将综述目前常用的路径规划算法，包括Dijkstra算法、A*算法、Bellman-Ford算法和Floyd-Warshall算法，并分析其优缺点及应用场景。
1. Dijkstra算法Dijkstra算法是一种求解单源最短路径的经典算法。
它的基本思想是从起点开始，逐步扩展搜索范围，直到找到最短路径。
Dijkstra算法通过维护一个优先队列来选择当前距离起点最近的节点进行扩展，直到找到目标节点或搜索完所有节点。
该算法适用于无向图或有向图中有正权边的情况。
Dijkstra算法的时间复杂度为O((V + E) log V)，其中V是节点数，E是边数。
2. A*算法A*算法是一种启发式搜索算法，结合了Dijkstra算法和贪心算法的思想。
它引入了启发函数来指导搜索方向，以减少搜索空间。
在A*算法中，每个节点都有一个估计值，表示该节点到目标节点的预计代价。
算法通过维护一个优先队列来选择当前估计代价最小的节点进行扩展，直到找到目标节点。
A*算法的时间复杂度与Dijkstra算法相同，但在实际应用中通常具有更好的性能。
3. Bellman-Ford算法Bellman-Ford算法是一种求解单源最短路径的动态规划算法。
它通过使用松弛操作来逐步更新节点的最短路径估计值，直到收敛为止。
Bellman-Ford算法适用于解决带有负权边的图中的单源最短路径问题，但要求没有负环路。
该算法的时间复杂度为O(VE)，其中V是节点数，E是边数。
4. Floyd-Warshall算法Floyd-Warshall算法是一种求解全源最短路径的动态规划算法。
它通过使用中间节点来逐步更新节点间的最短路径估计值，直到得到全局最短路径。
Floyd-Warshall算法适用于解决带有负权边的图中的全源最短路径问题，但要求没有负环路。
最短路算法
最短路问题
一 、狄克斯特拉算法 (Dijkstra algorithm, 1959)
• 计算两节点之间或一个节点到所有节点之间的最短路
的直接距离(两点之间有边 两点之间有边)， 令 dij 表示 vi 到 vj 的直接距离 两点之间有边 ，若两点之间 没有边， 两点之间是有向边， 没有边，则令 dij = ∞，若两点之间是有向边，则 dji = ∞； 令 dii = 0，s 表示始点，t 表示终点 ， 表示始点，
j dij i dik djk k
4
6.3.2 Floyd-Warshall 算法 (1962) for i=1 to n do dii=∞; ∞ for all eij=0; for j=1 to n do for i=1 to n do if i≠j then ≠ for k=1 to n do if k≠j then ≠ begin dik=min{dik, dij+djk}; if dik>dij+djk then eik=j end;
1
例1 狄克斯特拉算法 ∞ 10 11 ∞
2 10
0 s
1 8 9 3 4
12 15 ∞
5 20 2 2 30
∞ t 31
பைடு நூலகம்15
8 4 ∞ 8
7
6
13 ∞ 15
2
Dijkstra最短路算法的特点和适应范围 最短路算法的特点和 最短路算法的特点
• 一种隐阶段的动态规划方法 • 每次迭代只有一个节点获得永久标记，若有两个或两个以上 每次迭代只有一个节点获得永久标记， 节点的临时标记同时最小，可任选一个永久标记；总是从一 节点的临时标记同时最小，可任选一个永久标记； 个新的永久标记开始新一轮的临时标记，是一种深探法 个新的永久标记开始新一轮的临时标记，是一种深探法 • 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij≥0， 的最短路， ， 次迭代得到的永久标记， 条边， 第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因 此最多有n 此最多有 −1 次迭代 • 可以应用于简单有向图和混合图，在临时标记时，所谓相邻 可以应用于简单有向图和混合图 在临时标记时， 简单有向图和混合图， 必须是箭头指向的节点； 必须是箭头指向的节点；若第 n−1 次迭代后仍有节点的标记 为 ∞，则表明 vs 到该节点无有向路径 • 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束 的最短路， 了；但算法复杂度是一样的 • 应用 Dijkstra 算法 n−1 次 ，可以求所有点间的最短路 • vs 到所有点的最短路也是一棵生成树，但不是最小生成树 到所有点的最短路也是一棵生成树，
一 、狄克斯特拉算法 (Dijkstra algorithm, 1959)
• 计算两节点之间或一个节点到所有节点之间的最短路
的直接距离(两点之间有边 两点之间有边)， 令 dij 表示 vi 到 vj 的直接距离 两点之间有边 ，若两点之间 没有边， 两点之间是有向边， 没有边，则令 dij = ∞，若两点之间是有向边，则 dji = ∞； 令 dii = 0，s 表示始点，t 表示终点 ， 表示始点，
j dij i dik djk k
4
6.3.2 Floyd-Warshall 算法 (1962) for i=1 to n do dii=∞; ∞ for all eij=0; for j=1 to n do for i=1 to n do if i≠j then ≠ for k=1 to n do if k≠j then ≠ begin dik=min{dik, dij+djk}; if dik>dij+djk then eik=j end;
1
例1 狄克斯特拉算法 ∞ 10 11 ∞
2 10
0 s
1 8 9 3 4
12 15 ∞
5 20 2 2 30
∞ t 31
பைடு நூலகம்15
8 4 ∞ 8
7
6
13 ∞ 15
2
Dijkstra最短路算法的特点和适应范围 最短路算法的特点和 最短路算法的特点
• 一种隐阶段的动态规划方法 • 每次迭代只有一个节点获得永久标记，若有两个或两个以上 每次迭代只有一个节点获得永久标记， 节点的临时标记同时最小，可任选一个永久标记；总是从一 节点的临时标记同时最小，可任选一个永久标记； 个新的永久标记开始新一轮的临时标记，是一种深探法 个新的永久标记开始新一轮的临时标记，是一种深探法 • 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij≥0， 的最短路， ， 次迭代得到的永久标记， 条边， 第 k 次迭代得到的永久标记，其最短路中最多有 k 条边，因 此最多有n 此最多有 −1 次迭代 • 可以应用于简单有向图和混合图，在临时标记时，所谓相邻 可以应用于简单有向图和混合图 在临时标记时， 简单有向图和混合图， 必须是箭头指向的节点； 必须是箭头指向的节点；若第 n−1 次迭代后仍有节点的标记 为 ∞，则表明 vs 到该节点无有向路径 • 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束 的最短路， 了；但算法复杂度是一样的 • 应用 Dijkstra 算法 n−1 次 ，可以求所有点间的最短路 • vs 到所有点的最短路也是一棵生成树，但不是最小生成树 到所有点的最短路也是一棵生成树，
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
D[v][w] = D[v][k] + D[k][w];
for (i = 0; i < G.vexnum; i++)
P[v][w][i] = P[v][k][i] || P[k][w][i];
}
for(a=0; a<G.vexnum; a++)
for(b=0; b<G.vexnum; b++)
if(D[a][b] < INFINITY && a!=b){
U=<F>
A→C→E→F=12(比上面第四步的A→C→D→F=9要长)此时到F权值更改为A→C→D→F=9
发现A→C→D→F=9权值为最短
6
选入F，此时S=<A、C、B、D、E、F>
此时最短路径A→A=0，A→C=3，
A→C→B=5，
A→C→D=6，
A→C→E=7，A→C→D→F=9
U集合已空，查找完毕。
最短路径之Dijkstra算法详细讲解
１最短路径算法
在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
// D[v][w]从v到w的最短路径的长度
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++){
D[v][w] = G.arcs[v][w];
for (k = 0; k < G.vexnum; k++)
P[v][w][k] = FALSE;
U=<E、F>
A→C→D→E=8(比上面第二步的A→C→E=7要长)此时到E权值更改为A→C→E=7，A→C→D→F=9
发现A→C→E=7权值为最短
5
选入E，此时S=<A、C、B、D、E>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E为中间点，
从A→C→E=7这条最短路径开始找
find(P,G,a,k);
printf("\t%c",65+k);
find(P,G,k,b);
}
}
采用递归的思想一次寻找是否存在中间点然后打印出来。
问题出在红色部分，判定是否采用递归，未考虑k是否与a b相同，结果导致无限递归。从而发现stack overflow的错误提示有可能出于递归无法跳出，导致栈的溢出问题。
A→C→B=5(比上面第一步的A→B=6要短)
此时到D权值更改为A→C→B=5，
A→C→D=6，
A→C→E=7，
A→C→其它U中的顶点=∞，发现A→C→B=5权值为最短
3
选入B，此时S=<A、C、B>
此时最短路径A→A=0，A→C=3，A→C→B=5
以B为中间点
从A→C→B=5这条最短路径开始找
U=<D、E、F>
2.3 Dijkstra算法具体步骤
（1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
Floyd算法
实现Floyd算法，并求所示有向图中各顶点之间的最短路径及其长度。
算法思想
采用图的邻接矩阵存储，实现Floyd算法~，数组P[][][]存储是否存在中间点使长度缩短。
设计描述
数据存储结构类型的定义：
typedef struct MGraph{
char vexs[MAX_VERTEX_NUM];
A→C→B→D=10(比上面第二步的A→C→D=6要长)
此时到D权值更改为A→C→D=6，
A→C→B→其它U中的顶点=∞，发现A→C→D=6权值为最短
4
选入D，此时S=<A、C、B、D>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6
以D为中间点，
从A→C→D=6这条最短路径开始找
步骤
S集合中
U集合中
1
选入A，此时S=<A>
此时最短路径A→A=0
以A为中间点，从A开始找
U=<B、C、D、E、F>
A→B=6，A→C=3，
A→其它U中的顶点=∞，
发现A→C=3权值为最短
2
选入C，此时S=<A、C>
此时最短路径A→A=0，A→C=3以C为中间点，
从A→C=3这条最短路径开始找
U=<B、D、E、F>
if (D[v][w] < INFINITY)
P[v][w][v] = P[v][w][w] = TRUE;
}
for (k = 0; k < G.vexnum; k++)
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
if (D[v][k] + D[k][w] < D[v][w]){
２Dijkstra算法
2.1 Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹入邻接矩阵\n");
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
scanf("%d",&G.arcs[v][w]); //读入邻接矩阵
// P[v][w][k]为TRUE，则从v到w的最短路径中含有k节点
int k;
for(k = 0; k < G.vexnum; k++)
if(P[a][b][k]==TRUE && k!=a && k!=b){
find(P,G,a,k);
printf("%c\t",65+k);
find(P,G,k,b);
}
}
测试结果
输入
（1000为无穷！~
输出
心得体会~。！！
懂得了floyd算法的思想，用邻接矩阵存储带权值的图。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
2.4 Dijkstra算法举例说明
如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
图一：Dijkstra无向图
算法执行步骤如下表：【注：图片要是看不到请到“相册--日志相册”中，名为“Dijkstra算法过程”的图就是了】
printf("%c到%c最短路径为",65+a,65+b);
printf("%c\t",65+a);
find(P,G,a,b);
printf("%c\t",65+b);
printf("长度为%d",D[a][b]);
printf("\n");
}
}
void find(int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph G,int a,int b){
MGraph G;
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM],P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int v,w,k,a,b,i;
printf("请输入顶点数和弧数");
scanf("%d %d",&G.vexnum,&G.arcnum);
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
GraphKind kind;
}MGraph;
源程序
#include<stdlib.h>
#include<stdio.h>
#define INFINITY 1000 //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
（１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
（２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
（３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。
for (i = 0; i < G.vexnum; i++)
P[v][w][i] = P[v][k][i] || P[k][w][i];
}
for(a=0; a<G.vexnum; a++)
for(b=0; b<G.vexnum; b++)
if(D[a][b] < INFINITY && a!=b){
U=<F>
A→C→E→F=12(比上面第四步的A→C→D→F=9要长)此时到F权值更改为A→C→D→F=9
发现A→C→D→F=9权值为最短
6
选入F，此时S=<A、C、B、D、E、F>
此时最短路径A→A=0，A→C=3，
A→C→B=5，
A→C→D=6，
A→C→E=7，A→C→D→F=9
U集合已空，查找完毕。
最短路径之Dijkstra算法详细讲解
１最短路径算法
在日常生活中，我们如果需要常常往返A地区和B地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括：
// D[v][w]从v到w的最短路径的长度
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++){
D[v][w] = G.arcs[v][w];
for (k = 0; k < G.vexnum; k++)
P[v][w][k] = FALSE;
U=<E、F>
A→C→D→E=8(比上面第二步的A→C→E=7要长)此时到E权值更改为A→C→E=7，A→C→D→F=9
发现A→C→E=7权值为最短
5
选入E，此时S=<A、C、B、D、E>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6，A→C→E=7，以E为中间点，
从A→C→E=7这条最短路径开始找
find(P,G,a,k);
printf("\t%c",65+k);
find(P,G,k,b);
}
}
采用递归的思想一次寻找是否存在中间点然后打印出来。
问题出在红色部分，判定是否采用递归，未考虑k是否与a b相同，结果导致无限递归。从而发现stack overflow的错误提示有可能出于递归无法跳出，导致栈的溢出问题。
A→C→B=5(比上面第一步的A→B=6要短)
此时到D权值更改为A→C→B=5，
A→C→D=6，
A→C→E=7，
A→C→其它U中的顶点=∞，发现A→C→B=5权值为最短
3
选入B，此时S=<A、C、B>
此时最短路径A→A=0，A→C=3，A→C→B=5
以B为中间点
从A→C→B=5这条最短路径开始找
U=<D、E、F>
2.3 Dijkstra算法具体步骤
（1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。
（2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。
（3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边上的权。
Floyd算法
实现Floyd算法，并求所示有向图中各顶点之间的最短路径及其长度。
算法思想
采用图的邻接矩阵存储，实现Floyd算法~，数组P[][][]存储是否存在中间点使长度缩短。
设计描述
数据存储结构类型的定义：
typedef struct MGraph{
char vexs[MAX_VERTEX_NUM];
A→C→B→D=10(比上面第二步的A→C→D=6要长)
此时到D权值更改为A→C→D=6，
A→C→B→其它U中的顶点=∞，发现A→C→D=6权值为最短
4
选入D，此时S=<A、C、B、D>
此时最短路径A→A=0，A→C=3，A→C→B=5，A→C→D=6
以D为中间点，
从A→C→D=6这条最短路径开始找
步骤
S集合中
U集合中
1
选入A，此时S=<A>
此时最短路径A→A=0
以A为中间点，从A开始找
U=<B、C、D、E、F>
A→B=6，A→C=3，
A→其它U中的顶点=∞，
发现A→C=3权值为最短
2
选入C，此时S=<A、C>
此时最短路径A→A=0，A→C=3以C为中间点，
从A→C=3这条最短路径开始找
U=<B、D、E、F>
if (D[v][w] < INFINITY)
P[v][w][v] = P[v][w][w] = TRUE;
}
for (k = 0; k < G.vexnum; k++)
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
if (D[v][k] + D[k][w] < D[v][w]){
２Dijkstra算法
2.1 Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹入邻接矩阵\n");
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
scanf("%d",&G.arcs[v][w]); //读入邻接矩阵
// P[v][w][k]为TRUE，则从v到w的最短路径中含有k节点
int k;
for(k = 0; k < G.vexnum; k++)
if(P[a][b][k]==TRUE && k!=a && k!=b){
find(P,G,a,k);
printf("%c\t",65+k);
find(P,G,k,b);
}
}
测试结果
输入
（1000为无穷！~
输出
心得体会~。！！
懂得了floyd算法的思想，用邻接矩阵存储带权值的图。
（4）重复步骤（2）和（3）直到所有顶点都包含在S中。
2.4 Dijkstra算法举例说明
如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）
图一：Dijkstra无向图
算法执行步骤如下表：【注：图片要是看不到请到“相册--日志相册”中，名为“Dijkstra算法过程”的图就是了】
printf("%c到%c最短路径为",65+a,65+b);
printf("%c\t",65+a);
find(P,G,a,b);
printf("%c\t",65+b);
printf("长度为%d",D[a][b]);
printf("\n");
}
}
void find(int P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM],MGraph G,int a,int b){
MGraph G;
int D[MAX_VERTEX_NUM][MAX_VERTEX_NUM],P[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int v,w,k,a,b,i;
printf("请输入顶点数和弧数");
scanf("%d %d",&G.vexnum,&G.arcnum);
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int vexnum,arcnum;
GraphKind kind;
}MGraph;
源程序
#include<stdlib.h>
#include<stdio.h>
#define INFINITY 1000 //最大值
#define MAX_VERTEX_NUM 20 //最大顶点个数
（１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。
（２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。
（３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。