PTA数据结构天梯赛L2-001：手把手教你用Dijkstra算法搞定双权值最短路径（附C语言完整代码）

PTA数据结构天梯赛L2-001双权值最短路径的Dijkstra算法实战解析在算法竞赛和数据结构课程中图论问题一直是考察重点和难点。面对PTA天梯赛L2-001这类需要同时考虑时间和距离两个权值的最短路径问题传统的单权值Dijkstra算法需要经过巧妙改造才能满足题目要求。本文将深入剖析如何基于经典Dijkstra算法进行扩展处理双权值条件下的最优路径选择问题。1. 问题分析与算法选择题目要求为一个天梯赛在线地图实现路径推荐功能需要输出两条路线最快到达路线和最短距离路线。当存在多条相同时间的路径时选择其中距离最短的当存在多条相同距离的路径时选择经过节点最少的。这种双权值条件下的路径优化问题需要我们对传统最短路径算法进行针对性改造。关键问题特征每条边有两个权值通过时间和路径长度路径选择需要考虑主次优化目标需要输出完整路径而不仅仅是路径长度算法选择对比算法类型适用场景本题适用性Dijkstra单源非负权最短路径高度适用需改造Floyd多源最短路径不必要计算冗余Bellman-Ford含负权边的最短路径不适用无负权边A*搜索启发式路径搜索适用但实现复杂基于上述分析选择Dijkstra算法作为基础进行改造是最优方案。我们需要实现两个版本的Dijkstra时间优先的最短路径算法时间相同时选择距离短的路径距离优先的最短路径算法距离相同时选择节点少的路径2. 数据结构设计与输入处理高效的数据结构是算法实现的基础。针对题目输入特点我们采用邻接矩阵存储图结构并使用结构体封装边属性。#define MAX 32767 // 表示无穷大的值 typedef struct { int length; // 路径长度 int time; // 通过时间 } Edge; int main() { int n, m; // n:节点数, m:边数 scanf(%d %d, n, m); // 初始化邻接矩阵 Edge graph[n][n]; for(int i 0; i n; i) { for(int j 0; j n; j) { graph[i][j].time MAX; graph[i][j].length MAX; } } // 读取边信息 for(int i 0; i m; i) { int x, y, one_way, len, t; scanf(%d %d %d %d %d, x, y, one_way, len, t); graph[x][y].length len; graph[x][y].time t; if(one_way 0) { // 双向边 graph[y][x].length len; graph[y][x].time t; } } int start, end; scanf(%d %d, start, end); // 后续算法处理... }输入处理注意事项明确边的单向/双向性质未连接的边初始化为MAX(无穷大)节点编号从0开始连续分布3. 双权值Dijkstra算法实现3.1 时间优先的最短路径算法在时间优先的算法中当两条路径时间相同时我们需要选择距离更短的路径。这需要在传统的Dijkstra算法中加入额外的判断条件。typedef struct { int prev_node; // 前驱节点 int total_time; // 累计时间 int total_length; // 累计距离 } TimePriorityPath; void dijkstra_time_priority(int start, int n, Edge graph[n][n], TimePriorityPath paths[n]) { int visited[n]; // 标记已确定最短路径的节点 for(int i 0; i n; i) { paths[i].prev_node -1; paths[i].total_time MAX; paths[i].total_length MAX; visited[i] 0; } paths[start].total_time 0; paths[start].total_length 0; for(int i 0; i n; i) { // 找出未访问节点中时间最短的 int min_node -1; int min_time MAX; for(int j 0; j n; j) { if(!visited[j] paths[j].total_time min_time) { min_time paths[j].total_time; min_node j; } } if(min_node -1) break; visited[min_node] 1; // 更新邻接节点 for(int j 0; j n; j) { if(graph[min_node][j].time MAX) { // 存在边 int new_time paths[min_node].total_time graph[min_node][j].time; int new_length paths[min_node].total_length graph[min_node][j].length; if(new_time paths[j].total_time) { paths[j].total_time new_time; paths[j].total_length new_length; paths[j].prev_node min_node; } else if(new_time paths[j].total_time new_length paths[j].total_length) { paths[j].total_length new_length; paths[j].prev_node min_node; } } } } }3.2 距离优先的最短路径算法在距离优先的算法中当两条路径距离相同时我们需要选择经过节点数更少的路径。这需要额外维护一个节点计数器。typedef struct { int prev_node; // 前驱节点 int total_length; // 累计距离 int node_count; // 路径节点数 } DistancePriorityPath; void dijkstra_distance_priority(int start, int n, Edge graph[n][n], DistancePriorityPath paths[n]) { int visited[n]; for(int i 0; i n; i) { paths[i].prev_node -1; paths[i].total_length MAX; paths[i].node_count 0; visited[i] 0; } paths[start].total_length 0; paths[start].node_count 1; for(int i 0; i n; i) { // 找出未访问节点中距离最短的 int min_node -1; int min_length MAX; for(int j 0; j n; j) { if(!visited[j] paths[j].total_length min_length) { min_length paths[j].total_length; min_node j; } } if(min_node -1) break; visited[min_node] 1; // 更新邻接节点 for(int j 0; j n; j) { if(graph[min_node][j].length MAX) { // 存在边 int new_length paths[min_node].total_length graph[min_node][j].length; int new_count paths[min_node].node_count 1; if(new_length paths[j].total_length) { paths[j].total_length new_length; paths[j].node_count new_count; paths[j].prev_node min_node; } else if(new_length paths[j].total_length new_count paths[j].node_count) { paths[j].node_count new_count; paths[j].prev_node min_node; } } } } }4. 路径重构与输出处理获得最短路径信息后我们需要从终点回溯到起点重构完整路径并按照题目要求的格式输出。void reconstruct_path(int start, int end, int prev_nodes[], int path[]) { int current end; int path_length 0; // 反向存储路径 while(current ! start) { path[path_length] current; current prev_nodes[current]; } path[path_length] start; // 现在path中存储的是end-...-start } void print_path(int path[], int length, const char* type, int value) { printf(%s %d: , type, value); for(int i length; i 0; i--) { printf(%d, path[i]); if(i 0) printf( ); } printf(\n); } int main() { // ...之前的输入处理代码... TimePriorityPath time_paths[n]; DistancePriorityPath dist_paths[n]; dijkstra_time_priority(start, n, graph, time_paths); dijkstra_distance_priority(start, n, graph, dist_paths); int time_route[n], dist_route[n]; reconstruct_path(start, end, time_paths, time_route); reconstruct_path(start, end, dist_paths, dist_route); // 计算路径长度 int time_len 0; while(time_route[time_len] ! start) time_len; int dist_len 0; while(dist_route[dist_len] ! start) dist_len; // 检查两条路径是否相同 int is_same 1; if(time_len ! dist_len) { is_same 0; } else { for(int i 0; i time_len; i) { if(time_route[i] ! dist_route[i]) { is_same 0; break; } } } // 按照题目要求格式输出 if(is_same) { printf(Time %d; Distance %d: , time_paths[end].total_time, dist_paths[end].total_length); for(int i time_len; i 0; i--) { printf(%d, time_route[i]); if(i 0) printf( ); } printf(\n); } else { print_path(time_route, time_len, Time, time_paths[end].total_time); print_path(dist_route, dist_len, Distance, dist_paths[end].total_length); } return 0; }5. 算法优化与性能分析对于节点数N≤500的规模上述O(N²)的Dijkstra实现已经足够。但在实际竞赛中我们可以考虑以下优化优先队列优化使用最小堆可以将时间复杂度优化到O(MlogN)其中M是边数。C语言中需要手动实现优先队列// 最小堆实现示例 typedef struct { int node; int value; // 时间或距离 } HeapNode; void heap_push(HeapNode heap[], int* size, HeapNode item) { heap[(*size)] item; int current *size; while(current 1 heap[current].value heap[current/2].value) { HeapNode temp heap[current]; heap[current] heap[current/2]; heap[current/2] temp; current / 2; } } HeapNode heap_pop(HeapNode heap[], int* size) { HeapNode result heap[1]; heap[1] heap[(*size)--]; int current 1; while(1) { int child current * 2; if(child *size) break; if(child 1 *size heap[child1].value heap[child].value) { child; } if(heap[current].value heap[child].value) break; HeapNode temp heap[current]; heap[current] heap[child]; heap[child] temp; current child; } return result; }空间优化技巧对于稀疏图使用邻接表而非邻接矩阵存储复用数组减少内存分配使用位运算压缩状态信息常见错误排查未正确初始化距离数组应初始化为INF忽略双向边的处理路径重构时未正确处理起点未考虑多条等价路径时的选择条件在实际竞赛中这类题目通常会设置严格的运行时间限制。对于N500的情况O(N²)的实现大约需要每次Dijkstra运算500² 250,000次操作两次Dijkstra500,000次操作在现代CPU上约需几毫秒完全在合理范围内