新网做网站流程,互联网网站备案,怎样选择网站服务器,python基础教程免费下载前置知识#xff1a;最小生成树#xff0c;图的遍历 最短路径
当图是带权图时#xff0c;把从一个顶点 v 0 v_0 v0到图中其余任意一个顶点 v i v_i vi的一条路径所经过边上的权值之和#xff0c;定位为该路径的带权路径长度#xff0c;把带权路径长度最短的那条路径最小生成树图的遍历 最短路径
当图是带权图时把从一个顶点 v 0 v_0 v0到图中其余任意一个顶点 v i v_i vi的一条路径所经过边上的权值之和定位为该路径的带权路径长度把带权路径长度最短的那条路径不唯一称为最短路径。 求解最短路径的算法通常都依赖于一种性质即两点之间的最短路径也包含了路径上其他顶点之间的最短路径。带权有向图 G G G的最短路径问题一般可分为两类一类是单源最短路径顾名思义“单个源头”即求从图中某一顶点到其他各顶点的最短路径可通过经典的 D i j k s t r a Dijkstra Dijkstra迪杰斯特拉算法求解另一类是求每对顶点间的最短路径可通过 F l o y e d Floyed Floyed弗洛伊德算法来求解。
回顾BFS算法求解单源最短路径
广度优先搜索查找最短路径只是对无权图而言的。 无权图可以视为一种特殊的带权图只是每条边的权值为 1 1 1。 若图 G ( V , E ) G(V,E) G(V,E)为无权图定义从顶点 u u u到顶点 v v v的最短路径 d ( u , v ) d(u,v) d(u,v)为 u u u到 v v v的任何路径中最少的边数若从 u u u到 v v v没有通路则 d ( u , v ) ∞ d(u,v)\infin d(u,v)∞。 使用 B F S BFS BFS我们可以求解一个满足上述定义的“无权图的单源最短路径问题”这是由广度优先搜索总是按照距离由近到远来遍历图中每个顶点的性质决定的。 首先是预处理使用邻接表对图进行存储。
#define MaxVertexNum 810
#define INF 0x7fffffff
//INF就是无穷大typedef struct ArcNode {int adjvex;struct ArcNode* nextarc;
}ArcNode;
typedef struct VNode {int data;ArcNode* firstarc;
}VNode, AdjList[MaxVertexNum];
typedef struct {AdjList vertices;//邻接表存储图int vexnum, arcnum;
}ALGraph;
bool Visited[MaxVertexNum];//辅助数组标记顶点是否被访问typedef struct LinkNode {int Vertex;//图的顶点编号struct LinkNode* next;
}LinkNode;
typedef struct {LinkNode* front, * rear;//链队列
}LinkQueue;void InitQueue(LinkQueue Q) {LinkNode* p (LinkNode*)malloc(sizeof(LinkNode*));p-Vertex -1;p-next NULL;Q.front Q.rear p;//初始化队列return;
}bool Q_Is_Empty(LinkQueue Q) {//队列判空return Q.front Q.rear ? true : false;
}void EnQueue(LinkQueue Q, int i) {//新元素入队LinkNode* p (LinkNode*)malloc(sizeof(LinkNode*));p-Vertex i;p-next NULL;Q.rear-next p;Q.rear p;return;
}void DeQueue(LinkQueue Q, int x) {//队头元素出队LinkNode* p Q.front-next;x p-Vertex;Q.front-next p-next;if (Q.rear p)Q.rear Q.front;free(p);return;
}B F S BFS BFS求解单源最短路径问题即求顶点 u u u到其他顶点的最短路径。
//求顶点u到其他顶点的最短路径
void BFS_MIN_Distance(ALGraph G, LinkQueue Q, int u) {int d[MaxVertexNum], path[MaxVertexNum], v;//d[i]表示从u到i结点的最短路径path[i]表示顶点u到顶点i的最短路径上顶点i的直接前驱memset(d, INF, sizeof(d));//初始化路径长度为无穷大memset(path, -1, sizeof(path));//初始化所有顶点的直接前驱为-1Visited[u] true, d[u] 0;EnQueue(Q, u);while (!Q_Is_Empty(Q)) {//BFS主过程DeQueue(Q, u);//队头元素出队for (ArcNode* w G.vertices[u].firstarc; w ! NULL; w w-nextarc) {//遍历u的所有邻接点v w-adjvex;if (!Visited[v]) {//若未访问Visited[v] true;//标记访问d[v] d[u] 1;//路径长度加1path[v] u;//最短路径中应是从u到vEnQueue(Q, v);//顶点w入队}}}return;
}B F S BFS BFS的完整代码可以看我的Github传送门
其中数组 d [ ] d[\ ] d[ ]是用来记录每一个顶点到原始顶点的最短路径的长度而数组 p a t h [ ] path[\ ] path[ ]则是用来记录每一个顶点在这个最短路径上的直接前驱。通过 p a t h [ ] path[\ ] path[ ]数组可以从某一个顶点出发一直逆向找到原始顶点从而确定最短路径上经过的所有顶点。 知识点回顾广度优先生成树 以原始顶点为根节点对无权图构建一棵广度优先生成树它的深度高度一定是最小的各顶点所在的层数也直接反映了原始顶点到该顶点的距离。 D i j k s t r a Dijkstra Dijkstra算法求解单源最短路径问题 D i j k s t r a Dijkstra Dijkstra算法通过设置一个集合 S S S记录已求得的最短路径的顶点。初始时把源点 v 0 v_0 v0放入 S S S集合 S S S每并入一个新顶点 v i v_i vi都要修改源点到集合 V − S V-S V−S中顶点当前的最短路径长度值。 构造过程中设置三个辅助数组 f i n a l [ ] final[\ ] final[ ]标记各顶点是否已找到最短路径即是否已归入集合 S S S。 d i s t [ ] dist[\ ] dist[ ]记录从源点 v 0 v_0 v0到其他各顶点当前的最短路径长度它的初始值为若从 v 0 v_0 v0到 v i v_i vi有弧则 d i s t [ i ] dist[i] dist[i]为弧上的权值否则置 d i s t [ i ] dist[i] dist[i]为 ∞ \infin ∞。 p a t h [ ] path[\ ] path[ ] p a t h [ i ] path[i] path[i]表示从源点到顶点 i i i之间的最短路径的前驱结点。在算法结束时可根据其值追溯得到源点 v 0 v_0 v0到顶点 v i v_i vi的最短路径。
假设从顶点 0 0 0出发即 v 0 0 v_00 v00集合 S S S最初只包含顶点 0 0 0邻接矩阵 a r c s arcs arcs表示带权有向图 a r c s [ i ] [ j ] arcs[i][j] arcs[i][j]表示有向边 i , j i,j i,j的权值若不存在有向边 i , j i,j i,j则 a r c s [ i ] [ j ] arcs[i][j] arcs[i][j]为 ∞ \infin ∞。 D i j k s t r a Dijkstra Dijkstra算法的步骤如下不考虑对 p a t h [ ] path[\ ] path[ ]的操作
初始化集合 S S S初始为 0 {0} 0 d i s t [ ] dist[\ ] dist[ ]初始值 d i s t [ i ] a r c s [ 0 ] [ i ] , i 1 , 2 , ⋯ , n − 1 dist[i]arcs[0][i],\ i1,2,\cdots ,n-1 dist[i]arcs[0][i], i1,2,⋯,n−1。从顶点集合 V − S V-S V−S中选出 v j v_j vj满足 d i s t [ j ] M i n { d i s t [ i ] ∣ v i ∈ V − S } dist\left[ j \right]Min\left\{ dist\left[ i \right]\left| {{v}_{i}}\in V-S \right. \right\} dist[j]Min{dist[i]∣vi∈V−S} v j v_j vj就是当前求得的一条从 v 0 v_0 v0出发的最短路径的终点令 S S ⋃ { j } SS\bigcup \left\{ j \right\} SS⋃{j}。修改从 v 0 v_0 v0出发到集合 V − S V-S V−S上任意一个顶点 v k v_k vk可达的最短路径长度若 d i s t [ j ] a r c s [ j ] [ k ] d i s t [ k ] dist\left[ j \right]arcs\left[ j \right]\left[ k \right]dist\left[ k \right] dist[j]arcs[j][k]dist[k]则更新 d i s t [ k ] d i s t [ j ] a r c s [ j ] [ k ] dist\left[ k \right]dist\left[ j \right]arcs\left[ j \right]\left[ k \right] dist[k]dist[j]arcs[j][k]。
下面是王道书上的一个关于实例的讲解读者可以自己耐心看看理解一下 D i j k s t r a Dijkstra Dijkstra算法的执行过程。 图片来自王道考研408数据结构2025 显然 D i j k s t r a Dijkstra Dijkstra算法也是基于贪心策略的。 使用邻接矩阵表示时时间复杂度为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。使用带权的邻接表表示时虽然修改 d i s t [ ] dist[\ ] dist[ ]的时间可以减少但由于在 d i s t [ ] dist[\ ] dist[ ]中选择最小分量的时间不变所以时间复杂度仍为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。 即使只求解从源点到特定顶点的最短路径时间复杂度依旧为 O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)。 注意边上带有负权值时 D i j k s t r a Dijkstra Dijkstra算法将失效。既有可能出现有更短的路径而无法修改的情况也有可能出现负环而导致死循环的情况。 对前一种情况例如 v 0 − v 1 10 , v 0 − v 2 7 , v 1 − v 2 − 5 v_0-v_110,\ v_0-v_27,\ v_1-v_2-5 v0−v110, v0−v27, v1−v2−5 D i j k s t r a Dijkstra Dijkstra算法会将 d i s t [ 2 ] dist[2] dist[2]置为 7 7 7而后无法更新实际上有一条距离更短的路径存在 对后一种情况例如 v 0 − v 1 1 , v 1 − v 0 − 2 , v 1 − v 2 1 v_0-v_11,\ v_1-v_0-2,\ v_1-v_21 v0−v11, v1−v0−2, v1−v21此时 v 0 v_0 v0和 v 1 v_1 v1之间构成一段负环越走路径长度越小会导致 D i j k s t r a Dijkstra Dijkstra算法陷入死循环 思考 D i j k s t r a Dijkstra Dijkstra算法与 P r i m Prim Prim算法有何异同之处 答 D i j k s t r a Dijkstra Dijkstra算法的流程、操作与 P r i m Prim Prim算法都很相似核心思想都是基于贪心策略实现。区别在于 ①目的不同 D i j k s t r a Dijkstra Dijkstra算法的目的是构建单源点的最短路径树 P r i m Prim Prim算法的目的是构建最小生成树。 ②算法思路略有不同 P r i m Prim Prim算法从一个点开始每次选择权值最小的边将其连接到已构建的生成树上直至所有顶点都已加入而 D i j k s t r a Dijkstra Dijkstra算法每次找出到源点距离最近且为归入集合的点并把它归入集合同时以这个点为基础更新从源点到其他所有顶点的距离。 ③适用的图不同 P r i m Prim Prim算法只能用于带权无向图 D i j k s t r a Dijkstra Dijkstra算法可用于带权有向图或带权无向图权值必须非负。 时间复杂度不同两个算法的时间复杂度之间有所不同。 F l o y e d Floyed Floyed算法求各顶点之间最短路径问题
求所有顶点之间的最短路径问题描述如下已知一个各边权值均非负的带权有向图对任意两个顶点 v i ≠ v j v_i≠v_j vivj要求求出 v i v_i vi与 v j v_j vj之间的最短路径和最短路径长度。 F l o y e d Floyed Floyed算法的实现基于动态规划 d p dp dp即把一个大问题分解为若干个性质相同但规模更小的子问题通过求解这些子问题的最优解进而求得大问题的最优解。类似于贪心但是贪心求解的是局部最优解可能会出现得不到全局最优解的情况而动态规划使用了状态转移方程能够较好地规避这个问题。关于动态规划的更多内容请参见动态规划基础 - OI Wiki。 F l o y e d Floyed Floyed算法的基本思想是递推产生一个 n n n阶方阵序列 A ( − 1 ) , A ( 0 ) , ⋯ , A ( k ) , ⋯ , A ( n − 1 ) {{A}^{\left( -1 \right)}},{{A}^{\left( 0 \right)}},\cdots ,{{A}^{\left( k \right)}},\cdots ,{{A}^{\left( n-1 \right)}} A(−1),A(0),⋯,A(k),⋯,A(n−1)其中 A ( k ) [ i ] [ j ] {A}^{(k)}[i][j] A(k)[i][j]表示从顶点 v i v_i vi到顶点 v j v_j vj之间的路径长度 k k k表示绕行第 k k k个顶点的运算步骤即增加第 k k k个顶点作为中继点 k − 1 k-1 k−1时表示无任何中继点。初始时对于任意两个顶点 v i v_i vi和 v j v_j vj若它们之间存在边则以此边上的权值作为它们之间的最短路径若不存在则置为 ∞ \infin ∞。之后逐步尝试在原路径中加入顶点 k k k k 0 , 1 , ⋯ , n − 1 k0,1,\cdots ,n-1 k0,1,⋯,n−1作为中继顶点。若增加中继顶点后得到的新路径比原来的路径长度要小则以此新路径代替原路径。算法描述如下
定义一个 n n n阶方阵序列 A ( − 1 ) , A ( 0 ) , ⋯ , A ( k ) , ⋯ , A ( n − 1 ) {{A}^{\left( -1 \right)}},{{A}^{\left( 0 \right)}},\cdots ,{{A}^{\left( k \right)}},\cdots ,{{A}^{\left( n-1 \right)}} A(−1),A(0),⋯,A(k),⋯,A(n−1)其中 A ( − 1 ) [ i ] [ j ] a r c s [ i ] [ j ] {{A}^{\left( -1 \right)}}\left[ i \right]\left[ j \right]arcs\left[ i \right]\left[ j \right] A(−1)[i][j]arcs[i][j] A ( k ) [ i ] [ j ] M i n { A ( k − 1 ) [ i ] [ j ] , A ( k − 1 ) [ i ] [ k ] A ( k − 1 ) [ k ] [ j ] } , k 0 , 1 , ⋯ , n − 1 {{A}^{\left( k \right)}}\left[ i \right]\left[ j \right]Min\left\{ {{A}^{\left( k-1 \right)}}\left[ i \right]\left[ j \right],{{A}^{\left( k-1 \right)}}\left[ i \right]\left[ k \right]{{A}^{\left( k-1 \right)}}\left[ k \right]\left[ j \right] \right\},k0,1,\cdots ,n-1 A(k)[i][j]Min{A(k−1)[i][j],A(k−1)[i][k]A(k−1)[k][j]},k0,1,⋯,n−1
式中 A ( 0 ) [ i ] [ j ] {{A}^{\left( 0 \right)}}\left[ i \right]\left[ j \right] A(0)[i][j]是从顶点 v i v_i vi到顶点 v j v_j vj、中继顶点是 v 0 v_0 v0的最短路径的长度。 A ( k ) [ i ] [ j ] {{A}^{\left( k \right)}}\left[ i \right]\left[ j \right] A(k)[i][j]是从顶点 v i v_i vi到 v j v_j vj、中继顶点是序号不大于 k k k的顶点的最短路径的长度。 F l o y e d Floyed Floyed算法是一个迭代的过程每迭代一次在从 v i v_i vi到 v j v_j vj的最短路径上就多考虑了一个顶点经过 n n n次迭代后所得到的 A ( n − 1 ) [ i ] [ j ] {{A}^{\left( n-1 \right)}}\left[ i \right]\left[ j \right] A(n−1)[i][j]就是 v i v_i vi到 v j v_j vj的最短路径长度即方阵 A ( n − 1 ) {{A}^{\left( n-1 \right)}} A(n−1)中就保存了任意一对顶点之间的最短路径长度。 下面是王道书上的一个关于实例的讲解读者可以自己耐心看看理解一下 F l o y e d Floyed Floyed算法的执行过程。当然我个人认为王道的课在这一块讲得更好比书上的东西更加清晰一些感兴趣的读者可以去看看相关视频王道计算机考研 数据结构 P67 6.4_4_最短路径问题_Floyed算法。 图片来自王道考研408数据结构2025 其核心代码实现其实非常简单
for (int k 0; k n; k)for (int i 0; i n; i)for (int j 0; j n; j)if (A[i][j] A[i][k] A[k][j])A[i][j] A[i][k] A[k][j], path[i][j] k;F l o y e d Floyed Floyed算法的时间复杂度为 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)。因为其代码结构简单紧凑不包含其他复杂的数据结构因此隐含的常数系数是很小的不容易被卡常对中等规模的输入来说它仍然是相当有效的。 F l o y e d Floyed Floyed算法允许图中有带负权值的边但不允许有负权回路这样的图里可能不存在最短路。 F l o y e d Floyed Floyed算法同样适用于带权无向图。 求各顶点之间最短路径问题也可以使用 D i j k s t r a Dijkstra Dijkstra算法前提是图中没有负权值的边。依次将所有顶点都作为源点分别运行一次 D i j k s t r a Dijkstra Dijkstra算法时间复杂度同样为 O ( ∣ V ∣ 3 ) O(|V|^3) O(∣V∣3)。当然 D i j k s t r a Dijkstra Dijkstra算法可以使用 堆/优先队列 优化使得时间复杂度从 O ( n 2 ) O(n^2) O(n2)降到 O ( n l o g n ) O(nlogn) O(nlogn) n ∣ V ∣ n|V| n∣V∣不过408考研初试并不需要掌握这么高级的东西。
相关例题【洛谷P3371】【模板】单源最短路径弱化版 解题报告
这篇博客是我对 D i j k s t r a Dijkstra Dijkstra算法的应用感兴趣的读者可以看看。另外我也写了这题 F l o y e d Floyed Floyed算法的40分解法完整代码可以参看我的Github传送门。核心代码如下
for (int k 1; k n; k)for (int i 1; i n; i)for (int j 1; j n; j)if (A[i][j] A[i][k] A[k][j])A[i][j] A[i][k] A[k][j], path[i][j] k;另外求解最短路径问题的算法还有 B e l l m a n − f o r d Bellman-ford Bellman−ford算法 S P F A SPFA SPFA算法等408考研初试也并不要求掌握这些。不过我以前打 O I OI OI的时候学过所以提一嘴实际上我以前学的也不好就是了。 408考研初试中对这部分主要考察手动推算相关算法的执行过程对代码的考查频率较低。 以上。
