四平公司做网站wordpress 字体定义

四平公司做网站,wordpress 字体定义,海南建设培训网站,宁波自助建站公司本文献给#xff1a; 已掌握无向图基础#xff0c;希望理解如何在带权图中找到两点间最短路径的C语言学习者。本文将系统讲解两种经典的最短路径算法。 你将学到#xff1a; 最短路径问题的定义与核心概念Dijkstra算法#xff1a;解决单源、非负权图的最短路径Bellman-For…本文献给已掌握无向图基础希望理解如何在带权图中找到两点间最短路径的C语言学习者。本文将系统讲解两种经典的最短路径算法。你将学到最短路径问题的定义与核心概念Dijkstra算法解决单源、非负权图的最短路径Bellman-Ford算法处理单源、含负权边的最短路径算法对比与实战应用目录第一部分问题定义与核心概念1. 什么是最短路径第二部分图的存储带权图第三部分Dijkstra算法1. 核心思想2. 算法步骤朴素O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)实现/b3. C语言实现第四部分Bellman-Ford算法1. 核心思想2. 算法步骤3. C语言实现第五部分总结与对比算法对比表选择指南第一部分问题定义与核心概念1. 什么是最短路径在带权无向图G ( V , E , w ) G (V, E, w)G(V,E,w)中w : E → R w: E \rightarrow \mathbb{R}w:E→R为边权函数。从源点s ss到目标t tt的路径P ( s , v 1 , . . . , v k , t ) P (s, v_1, ..., v_k, t)P(s,v1​,...,vk​,t)的长度为路径上所有边权之和d i s t ( P ) ∑ i 0 k w ( v i , v i 1 ) dist(P) \sum_{i0}^{k} w(v_i, v_{i1})dist(P)i0∑k​w(vi​,vi1​)最短路径是所有s ss到t tt路径中长度最小的路径。关键术语单源最短路径求从一个源点s ss到图中所有其他顶点的最短距离。权值可正、可负实际问题中常为非负如距离、时间、成本。松弛操作最短路径算法的核心操作通过考察一条边来更新当前的最短距离估计。第二部分图的存储带权图在基础邻接矩阵/邻接表上需要增加权值信息。#defineMAX_V100#defineINF0x3f3f3f3f// 表示“无穷大”的一个较大数值// 邻接矩阵带权typedefstruct{intmatrix[MAX_V][MAX_V];// 存储权值INF表示无边intvertex_count;}GraphMatrixWeighted;voidinit_graph_weighted(GraphMatrixWeighted*g,intn){g-vertex_countn;for(inti0;in;i){for(intj0;jn;j){g-matrix[i][j](ij)?0:INF;// 自身距离为0}}}voidadd_edge_weighted(GraphMatrixWeighted*g,intu,intv,intweight){if(ug-vertex_count||vg-vertex_count)return;g-matrix[u][v]weight;g-matrix[v][u]weight;// 无向图}第三部分Dijkstra算法1. 核心思想贪心策略。维护一个集合S SS包含已确定最短距离的顶点。每次从未确定的顶点中选择距离源点s ss最近的顶点u uu加入S SS并用u uu来松弛其所有邻居的距离。要求所有边权非负。算法正确性依赖当边权非负时当前未确定顶点中距离最小的顶点其距离不可能再被其他未确定的顶点更新减小。2. 算法步骤朴素O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)实现初始化dist[s] 0dist[v] INFv ≠ svisited[v] false。循环|V|次a. 找到未访问顶点中dist最小的顶点u。b. 标记u为已访问 (visited[u] true)。c.松弛操作对u的每个邻居v如果dist[u] w(u, v) dist[v]则更新dist[v] dist[u] w(u, v)。循环结束dist[]数组即为源点到各点的最短距离。3. C语言实现// Dijkstra算法 (邻接矩阵朴素实现)voiddijkstra(GraphMatrixWeighted*g,intsrc,intdist[]){intvisited[MAX_V]{0};// 初始化for(inti0;ig-vertex_count;i){dist[i]INF;}dist[src]0;for(intcount0;countg-vertex_count;count){// 步骤1: 找到未访问的dist最小顶点intu-1;intmin_distINF;for(intv0;vg-vertex_count;v){if(!visited[v]dist[v]min_dist){min_distdist[v];uv;}}if(u-1)break;// 剩余顶点不可达visited[u]1;// 步骤2: 松弛u的所有邻居for(intv0;vg-vertex_count;v){if(!visited[v]g-matrix[u][v]!INF){intnew_distdist[u]g-matrix[u][v];if(new_distdist[v]){dist[v]new_dist;}}}}}算法复杂度时间复杂度O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)适合稠密图。空间复杂度O ( ∣ V ∣ ) O(|V|)O(∣V∣)。优化方向使用**优先队列最小堆**可将时间复杂度降为O ( ( ∣ V ∣ ∣ E ∣ ) log ⁡ ∣ V ∣ ) O((|V||E|) \log |V|)O((∣V∣∣E∣)log∣V∣)适合稀疏图。第四部分Bellman-Ford算法1. 核心思想动态规划/松弛。通过对所有边进行∣ V ∣ − 1 |V|-1∣V∣−1轮松弛操作逐步逼近最短路径。可以处理负权边并能检测出图中是否存在从源点可达的负权环。原理在无负权环的图中任意两点间的最短路径最多包含∣ V ∣ − 1 |V|-1∣V∣−1条边。因此通过∣ V ∣ − 1 |V|-1∣V∣−1轮全局松弛足以找到所有最短路径。2. 算法步骤初始化dist[s] 0dist[v] INFv ≠ s。进行∣ V ∣ − 1 |V|-1∣V∣−1轮迭代每轮遍历图中的所有边( u , v ) (u, v)(u,v)。对每条边执行松弛操作如果dist[u] w(u, v) dist[v]则更新dist[v] dist[u] w(u, v)。负权环检测再进行一轮所有边的遍历。如果仍有边能被松弛则说明图中存在从源点可达的负权环最短路径无意义。3. C语言实现// Bellman-Ford算法 (使用边列表存储图更合适此处为演示使用邻接矩阵遍历所有边)voidbellman_ford(GraphMatrixWeighted*g,intsrc,intdist[]){// 初始化for(inti0;ig-vertex_count;i){dist[i]INF;}dist[src]0;// 步骤1: 进行 |V|-1 轮松弛for(inti0;ig-vertex_count-1;i){// 遍历所有边 (u, v)for(intu0;ug-vertex_count;u){for(intv0;vg-vertex_count;v){if(g-matrix[u][v]!INF){// 存在边intnew_distdist[u]g-matrix[u][v];if(new_distdist[v]){dist[v]new_dist;}}}}}// 步骤2: 检测负权环 (可选如果需要检测)for(intu0;ug-vertex_count;u){for(intv0;vg-vertex_count;v){if(g-matrix[u][v]!INFdist[u]g-matrix[u][v]dist[v]){printf(图中存在从源点可达的负权环\n);return;}}}}算法复杂度时间复杂度O ( ∣ V ∣ ⋅ ∣ E ∣ ) O(|V| \cdot |E|)O(∣V∣⋅∣E∣)使用邻接矩阵为O ( ∣ V ∣ 3 ) O(|V|^3)O(∣V∣3)使用边列表为O ( ∣ V ∣ ⋅ ∣ E ∣ ) O(|V| \cdot |E|)O(∣V∣⋅∣E∣)。空间复杂度O ( ∣ V ∣ ) O(|V|)O(∣V∣)。第五部分总结与对比算法对比表特性Dijkstra算法Bellman-Ford算法适用图类型非负权图任意图可含负权边核心思想贪心动态规划/松弛时间复杂度O ( ∣ V ∣ 2 ) O(|V|^2)O(∣V∣2)或O ( ( ∣ V ∣ ∣ E ∣ ) log ⁡ ∣ V ∣ ) O((|V||E|)\log|V|)O((∣V∣∣E∣)log∣V∣)O ( ∣ V ∣ ⋅ ∣ E ∣ ) O(|V| \cdot |E|)O(∣V∣⋅∣E∣)空间复杂度O ( ∣ V ∣ ) O(|V|)O(∣V∣)O ( ∣ V ∣ ) O(|V|)O(∣V∣)功能求单源最短路径求单源最短路径可检测负权环优点在非负权图中效率高功能强大适用范围广缺点不能处理负权边时间复杂度高选择指南绝大多数情况边权非负优先使用Dijkstra算法尤其是堆优化版本。例如道路导航、网络路由。图含有负权边必须使用Bellman-Ford算法。例如金融套利模型、某些特殊约束问题。需要检测负权环使用 Bellman-Ford 算法。觉得文章有帮助别忘了 点赞 - 给我一点鼓励⭐ 收藏 ⭐- 方便以后查看 关注 - 获取更新通知标签#C语言#图论#最短路径#Dijkstra#Bellman-Ford#算法