This title slide is titled "Applications of Graph Theory Algorithms in Real-World Problems." The subtitle highlights two examples: Dijkstra for shortest paths in campus navigation and Prim for minimum-cost fiber optic wiring in new areas.

图论算法在实际问题中的应用

Dijkstra：校园导航最短路径 | Prim：新区光纤布线最小成本

Source: 课堂讲解PPT

This agenda slide outlines the presentation structure. It covers campus navigation shortest paths using Dijkstra's algorithm, minimum-cost wiring in a new area using Prim's algorithm (each with problem description, graph modeling, analysis, code, and results), followed by a summary of algorithm applications.

演示大纲

1. 1. 校园导航最短路径（Dijkstra）

问题描述、图建模、算法分析、代码实现、结果展示

2. 2. 新区布线最小成本（Prim）

问题描述、图建模、算法分析、代码实现、结果展示

3. 3. 总结

算法应用回顾与展望 Source: 图论作业PPT

This slide is the header for Section 01: Campus Navigation Shortest Path. It highlights using the Dijkstra algorithm to compute shortest walking paths from dormitories to teaching buildings, libraries, cafeterias, and similar campus spots.

第一部分：校园导航最短路径

01

校园导航最短路径

Dijkstra算法求解宿舍到教学楼图书馆食堂等最短步行路径

Source: Dijkstra算法讲解

The slide outlines key campus locations like dorms, teaching buildings, libraries, and cafeterias. It addresses the core problem of shortest walking path planning between them, targeting minimal travel time from dorms to optimize students' daily commutes.

实际问题

• 校园内关键地点：宿舍、教学楼、图书馆、食堂等
• 问题核心：各点间最短步行路径规划
• 目标明确：宿舍到各点最小步行时间
• 实际需求：学生日常出行时间优化

Source: 校园内宿舍、教学楼、图书馆、食堂等地点间最短路径问题。目标：从宿舍到各点的最短步行时间路径。

The slide illustrates graph theory modeling with an undirected weighted graph, where vertices represent locations like dormitory (D), teaching building (T), library (L), and cafeteria (C). Edge weights denote walking times, such as D-T: 5 minutes and D-L: 10 minutes.

图论建模

!Image

• 无向加权图：顶点=地点（D宿舍、T教学楼、L图书馆、C食堂）
• 边权=步行时间
• 示例：D-T:5min, D-L:10min

Source: Wikipedia

The slide covers Dijkstra's algorithm for single-source shortest paths in non-negative weight graphs. It details priority queue implementation with O((V+E)logV) complexity, greedy selection of the nearest unvisited vertex, and path optimization through relaxation.

算法选择与分析

• Dijkstra算法：单源最短路径，适用于非负权图。
• 优先队列实现：时间复杂度 O((V+E)logV)。
• 贪心策略：每次选最小距离未访顶点。
• 核心思想：通过松弛操作逐步优化路径。

Source: 校园导航最短路径（Dijkstra算法）

This slide outlines the core pseudocode logic of Dijkstra's algorithm in a table with steps, code snippets, and explanations. It covers initialization of the source distance and priority queue, followed by iteratively popping the minimum-distance node, relaxing its neighbors, and updating the queue until empty.

代码实现（核心逻辑）

{ "headers": [ "步骤", "伪代码", "说明" ], "rows": [ [ "1", "dist[源]=0; pq.push(源)", "初始化源点距离和优先队列" ], [ "2", "while pq:", "循环直到队列为空" ], [ "3", "u = pq.pop_min()", "取出最小距离节点u" ], [ "4", "for v in adj[u]:", "遍历u的邻接节点v" ], [ "5", "if dist[v] > dist[u] + w(u,v): dist[v] = dist[u] + w(u,v); pq.update(v)", "松弛并更新优先队列" ] ] }

Source: Dijkstra算法优先队列实现

The slide titled "结果展示" presents a table of shortest paths from starting point D to endpoints T, L, and C, with travel times in minutes. It lists: D→T (5 min), D→T→L (8 min), and D→T→L→C (12 min).

结果展示

{ "headers": [ "起点", "终点", "最短时间 (min)", "路径" ], "rows": [ [ "D", "T", "5", "D → T" ], [ "D", "L", "8", "D → T → L" ], [ "D", "C", "12", "D → T → L → C" ] ] }

This slide is a section header for Part 2: Minimizing Fiber Optic Cabling Costs in New Areas. It describes using Prim's algorithm to find the minimum spanning tree, achieving the lowest total fiber connection costs.

第二部分：新区光纤布线成本最小化

02

第二部分：新区光纤布线成本最小化

Prim算法求最小生成树，实现光纤连接总成本最小化

The slide outlines a real-world problem of laying fiber optic cables at different locations within a new district. It aims to ensure full connectivity among all points while minimizing total construction costs.

实际问题

• 新区内不同地点铺设光纤线路
• 确保所有点完全连通
• 最小化总建设成本

The workflow defines vertices as locations, sets edge weights based on cable/fiber construction costs, and builds an undirected connected weighted graph. The objective is to find the Minimum Spanning Tree (MST) connecting all vertices at minimal total cost.

图论建模

{ "headers": [ "步骤", "描述", "关键输出" ], "rows": [ [ "顶点定义", "将新区不同地点抽象为图的顶点", "V = {地点1, 地点2, ..., 地点n}" ], [ "边权重设定", "根据地点间铺设光纤/电缆的建设成本定义边及权重", "E = {(u,v): 成本}, w(u,v) = 建设成本" ], [ "图构建", "形成无向连通加权图，确保所有顶点可达", "G = (V, E, w) 无向连通加权图" ], [ "问题抽象", "目标：求最小生成树，连通所有顶点最小总成本", "MST：最小总权连通子图" ] ] }

Source: 无向连通加权图：顶点=地点，边权=建设成本。目标：最小生成树（MST），连通所有顶点最小总权。

The slide selects Prim's algorithm for building a Minimum Spanning Tree (MST) via greedily adding the smallest edge from any vertex. It optimizes implementation with a priority queue for O((V+E)logV) complexity, ideal for dense graphs (E ≈ V²).

算法选择与分析

• 算法选择：Prim算法构建最小生成树（MST）
• 核心思想：从任意顶点贪心添加最小边
• 实现优化：优先队列，O((V+E)logV)复杂度
• 适用场景：稠密图（E≈V²，高连接密度）

Source: Prim算法：MST构建，从任意点开始贪心添加最小边。优先队列实现：O((V+E)logV)。适用于稠密图。

This slide outlines the core logic of Prim's Minimum Spanning Tree algorithm in a table with steps, pseudocode, and explanations. It details initialization of keys and the MST set, a loop to add V-1 vertices by extracting the minimum-key vertex, and relaxing updates for its neighbors if a better edge weight is found.

代码实现（核心逻辑）

{ "headers": [ "步骤", "伪代码", "说明" ], "rows": [ [ "1. 初始化", "key[v]=∞, key[s]=0, inMST[s]=true;", "设置初始键值，s入MST" ], [ "2. 主循环", "for in 1..V-1:", "添加V-1个顶点到MST" ], [ "3. 选最小", "u = extractmin(key);", "提取key最小的未入MST顶点" ], [ "4. 遍历邻居", "for v in adj[u]:", "检查u所有邻接顶点" ], [ "5. 松弛更新", "if !inMST[v] && w(u,v)<key[v]:", "若更优则更新key[v]和parent[v]" ] ] }

Source: Prim算法伪代码

The "结果展示" slide presents key stats for a new area's fiber optic wiring minimum spanning tree, with a total cost of 45k Yuan. It includes 3 tree edges, a lowest edge cost of 10k (A-B), and a highest of 20k (C-D).

结果展示

• 45k: 总成本

新区光纤布线总成本（元）

• 3: 生成树边数

最小生成树包含边数量

• 10k: 最低边成本

最小成本连接边（A-B）

• 20k: 最高边成本

最大成本连接边（C-D） Source: Prim算法 - 最小生成树结果

The slide summarizes Dijkstra and Prim algorithms as graph theory tools for solving real-world optimization problems, stressing correct modeling and efficient implementation, while encouraging exploration of more graph algorithm applications. It thanks the audience for listening and invites questions and discussion.

总结与展望

Dijkstra & Prim：图论算法解决实际优化问题。

关键：正确建模 + 高效实现。

扩展：探索更多图算法应用！

Q&A

感谢聆听！欢迎提问与讨论。

Source: 图论算法实际应用