下载文档原格式
八年级数学上册---《最短路径问题》课堂设计最短路径问题（第一课时） 在我们的学习生活中，接触过很多“最值问题”：最多最少，最长最短。
思考以下两个问题：复习1：如图，连接A 、B 两点的所有连线中，哪条最短？为什么？答：路线2最短，因为两点的所有连线中，线段最短，简称：两点之间，线段最短 复习2：点P 是直线l 外一点，点P 与该直线l 上各点连接的所有线段中，哪条最短？为什么？答：PC 最短，因为连接直线外一点与直线上各点的所有线段中，垂线段最短。
设计意图：复习“两点之间，线段最短”和“垂线段最短”，为最短路径问题做好铺垫。
通过识别，也让学生有动态的思想，在比较中，找到最短路径。
lC PA B D教师：刚刚的两个问题都是识别最短路径，接下来，我们尝试通过画图，找到最短路径。
引例1：如图，在直线l上求作一点C，使得CA+CB最短。
教师：（1）点C是直线l上的一个动点。
我们不妨先画一个一般的点C，连接CA，CB，我们的目标：找到一个点C，使得CA+CB最小。
（2）观察几何画板的演示：当C在运动的过程中，线段CA，CB也在移动，观察：什么时候线段和最短？（3）同学们可以观察到：当C是线段AB和l的交点，即ACB共线时，CA+CB 最短。
依据是：两点之间，线段最短。
作图方法：连接AB，交直线l于点C，点C即为所求。
总结：从一般的点C出发，从运动变化的角度观察图形，并用到“两点之间，线段最短”解决问题。
教师：接下来，我们用这样的方法，研究数学史上经典的“牧马人饮马问题”。
例1：如图，牧马人从A地出发，到一条笔直的河边l 饮马，然后到B地，牧马人到河边的什么地方饮马，可使所走的路径最短？BAl练习：有两棵树位置如图，树的底部分别为A，B，地上有一只昆虫沿着A—B 的路径在地面上爬行。
小树顶D处一只小鸟想飞下来抓住小虫后，再飞到大树的树顶C处。
问小鸟飞至AB之间何处时，飞行距离最短，在图中画出该点的位置。
最短路径课程设计一、课程目标知识目标：1. 理解最短路径的概念，掌握其在现实生活中的应用；2. 学会使用Dijkstra算法和Floyd算法求解有向图和无向图的最短路径问题；3. 了解最短路径问题在实际问题中的应用和拓展。
技能目标：1. 能够运用所学算法解决简单的最短路径问题；2. 能够分析并优化最短路径算法，提高解决问题的效率；3. 能够运用数学语言和工具软件描述和求解最短路径问题。
情感态度价值观目标：1. 培养学生对图论和算法的兴趣，激发他们探索问题的热情；2. 培养学生合作交流、分享成果的团队精神；3. 培养学生运用数学知识解决实际问题的意识，提高他们的数学素养。
课程性质：本课程为选修课，旨在拓展学生的知识面，提高他们的数学应用能力。
学生特点：学生为八年级学生，已掌握基本的数学知识和逻辑思维能力，对新鲜事物充满好奇。
教学要求：结合学生特点，通过生动的案例导入，激发学生兴趣；采用问题驱动的教学方法，引导学生主动探究；注重理论与实践相结合，提高学生的实际操作能力。
在教学过程中，关注学生的个体差异，给予个性化指导，确保课程目标的实现。
将课程目标分解为具体的学习成果，便于教学设计和评估。
二、教学内容1. 图的基本概念：图的定义、顶点、边、路径、连通图、有向图与无向图。
2. 最短路径问题：最短路径的定义、性质及其在实际问题中的应用。
3. Dijkstra算法：算法原理、步骤、示例演示及编程实现。
4. Floyd算法：算法原理、步骤、示例演示及编程实现。
5. 最短路径问题的拓展：多源最短路径、带有权重和负权边的最短路径问题。
6. 教学案例：结合实际生活中的问题，如交通网络、计算机网络等，分析最短路径问题。
7. 教学实践：运用算法解决具体的最短路径问题，对比不同算法的性能。
教学内容安排和进度：第一课时：图的基本概念及最短路径问题导入。
第二课时：Dijkstra算法原理及示例。
第三课时：Floyd算法原理及示例。
最短路径的课程设计一、课程目标知识目标：1. 学生能理解最短路径的概念，掌握其在现实生活中的应用。
2. 学生能掌握图论中关于最短路径的基本理论，如Dijkstra算法和Floyd算法。
3. 学生能运用所学算法解决实际问题，找出给定图中的最短路径。
技能目标：1. 学生能够运用数学思维分析图论问题，提出合理的解决方案。
2. 学生能够运用计算工具（如计算机软件）解决复杂的图论问题。
3. 学生通过小组合作，培养团队协作能力和沟通技巧。
情感态度价值观目标：1. 学生能够认识到数学在解决实际问题中的重要性，增强学习数学的兴趣和信心。
2. 学生在解决问题的过程中，培养勇于尝试、不断探索的精神。
3. 学生通过课程学习，体会团队合作的力量，树立合作共赢的价值观。
课程性质分析：本课程为中学数学课程，结合图论知识，旨在培养学生的逻辑思维能力和实际应用能力。
学生特点分析：初中生具有较强的求知欲和好奇心，喜欢探索新知识，但可能缺乏实际应用经验和团队协作能力。
教学要求：1. 教师应注重理论与实践相结合，提高学生的实际操作能力。
2. 教师应鼓励学生积极参与课堂讨论，培养他们的逻辑思维和表达能力。
3. 教师要关注学生的个体差异，因材施教，使每个学生都能在课程中收获成长。
二、教学内容本课程教学内容主要包括以下几部分：1. 图论基础知识：- 图的概念、分类及表示方法。
- 图的连通性、路径、回路等基本概念。
2. 最短路径算法：- Dijkstra算法：解决单源最短路径问题。
- Floyd算法：解决多源最短路径问题。
3. 实际应用案例分析：- 生活中的最短路径问题，如地图导航、网络路由等。
- 数学建模方法在实际问题中的应用。
4. 教学案例及练习：- 针对不同知识点设计教学案例，引导学生运用所学算法解决实际问题。
- 配合教材章节，提供适量练习题，巩固所学知识。
教学大纲安排如下：第1课时：图论基础知识- 知识点：图的表示方法、连通性、路径、回路。
求最短路径课程设计一、教学目标本章节的教学目标是使学生掌握求最短路径的方法和算法，能够运用这些方法解决实际问题。
具体目标如下：1.知识目标：–掌握最短路径问题的定义和意义。
–了解常见的最短路径算法，如Dijkstra算法、Bellman-Ford 算法等。
–理解图论中与最短路径相关的基本概念，如权值、边、顶点等。
2.技能目标：–能够运用Dijkstra算法和Bellman-Ford算法计算最短路径。
–能够分析不同算法的时间复杂度和空间复杂度。
–能够将最短路径算法应用到实际问题中，如地图导航、网络路由等。
3.情感态度价值观目标：–培养学生的逻辑思维能力和问题解决能力。
–培养学生对算法和计算机科学的兴趣和好奇心。
–培养学生团队合作和交流的能力，能够与他人共同解决问题。
二、教学内容本章节的教学内容主要包括最短路径问题的定义和意义、常见最短路径算法的原理和实现、以及最短路径算法在实际问题中的应用。
具体内容包括以下几个方面：1.最短路径问题的定义和意义：介绍最短路径问题的背景和定义，解释最短路径在实际中的应用场景。
2.常见最短路径算法：介绍Dijkstra算法和Bellman-Ford算法的原理和实现步骤，包括算法的时间复杂度和空间复杂度分析。
3.最短路径算法应用：通过实际案例，展示最短路径算法在地图导航、网络路由等领域的应用。
三、教学方法为了激发学生的学习兴趣和主动性，本章节将采用多种教学方法相结合的方式进行教学。
具体方法包括：1.讲授法：通过讲解最短路径问题的定义、算法原理和实现步骤，使学生掌握相关知识。
2.案例分析法：通过分析实际案例，使学生了解最短路径算法在现实中的应用。
3.实验法：安排上机实验，让学生动手实践，加深对最短路径算法的理解和掌握。
4.讨论法：学生进行分组讨论，促进学生之间的交流与合作，培养学生的团队合作能力。
四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，将采用以下教学资源：1.教材：选择一本与最短路径问题相关的教材，作为学生学习的基础资源。
课程设计最短路径问题一、课程目标知识目标：1. 让学生掌握最短路径问题的基本概念，理解其在现实生活中的应用。
2. 学会运用Dijkstra算法和Floyd算法解决最短路径问题。
3. 了解最短路径问题与其他优化问题的联系，拓展知识视野。
技能目标：1. 培养学生运用算法解决问题的能力，提高逻辑思维和计算思维能力。
2. 培养学生团队合作意识，学会在团队中分工合作，共同解决复杂问题。
3. 提高学生运用计算机软件（如Excel、编程语言等）处理数据的能力。
情感态度价值观目标：1. 培养学生面对问题的积极态度，勇于尝试和克服困难。
2. 增强学生对数学学科的兴趣和自信心，认识到数学在生活中的重要作用。
3. 培养学生具备良好的道德品质，遵循学术规范，尊重他人成果。
课程性质：本课程属于数学学科，以算法和实际应用为主线，结合计算机软件辅助教学。
学生特点：学生处于高年级阶段，具备一定的数学基础和逻辑思维能力，对算法和编程有一定了解。
教学要求：结合学生特点，课程要求注重理论与实践相结合，以学生为主体，引导他们主动探索和解决问题。
同时，关注学生的个性化差异，提供有针对性的指导和帮助。
通过本课程的学习，使学生能够达到上述课程目标，并在实际生活中运用所学知识解决问题。
二、教学内容1. 导入：通过实际生活中的最短路径问题（如导航系统、物流配送等）引出本节课的主题。
2. 基本概念：介绍最短路径问题的定义，包括加权图、路径长度等基本概念。
教材章节：第二章 图论基本概念3. 算法原理：a. Dijkstra算法：介绍单源最短路径算法原理，阐述其适用范围和限制。
b. Floyd算法：介绍多源最短路径算法原理，分析其时间复杂度。
教材章节：第三章 算法设计与分析4. 实践操作：a. 应用Dijkstra算法解决实际问题，如校园内两点间的最短路径。
b. 应用Floyd算法解决实际问题，如城市间最短路径规划。
教材章节：第四章 图论应用5. 计算机软件应用：运用Excel、编程语言（如Python、C++等）实现最短路径算法，分析实际数据。
c语言课程设计最短路径一、教学目标本节课的教学目标是让学生掌握C语言中最短路径算法的基本概念和实现方法。
具体包括以下三个方面：1.知识目标：使学生了解最短路径问题的背景和意义，理解Dijkstra算法和A*算法的原理，学会使用C语言实现最短路径算法。
2.技能目标：培养学生运用C语言解决实际问题的能力，提高学生的编程技巧和算法思维。
3.情感态度价值观目标：激发学生对计算机科学的兴趣，培养学生的创新精神和团队合作意识。
二、教学内容本节课的教学内容主要包括以下几个部分：1.最短路径问题的定义和意义：介绍最短路径问题的背景，让学生了解其在实际应用中的重要性。
2.Dijkstra算法：讲解Dijkstra算法的原理，演示算法的实现过程，让学生学会使用C语言实现Dijkstra算法。
3.A算法：介绍A算法的原理，讲解算法的优势和不足，让学生了解并掌握A*算法的实现方法。
4.算法优化：讨论如何优化算法，提高算法的效率，让学生学会在实际问题中灵活运用算法。
三、教学方法为了达到本节课的教学目标，将采用以下几种教学方法：1.讲授法：讲解最短路径问题的基本概念和算法原理，让学生掌握基本知识。
2.案例分析法：分析实际问题，让学生了解最短路径算法在实际应用中的价值。
3.实验法：让学生动手实践，学会使用C语言实现最短路径算法，提高编程能力。
4.讨论法：学生进行小组讨论，培养学生的团队合作意识和创新精神。
四、教学资源为了支持本节课的教学内容和教学方法，将准备以下教学资源：1.教材：《C语言程序设计》2.参考书：《数据结构与算法分析》3.多媒体资料：最短路径算法的动画演示4.实验设备：计算机、网络设备通过以上教学资源的支持，相信能够有效地帮助学生掌握最短路径算法，提高学生的编程能力。
五、教学评估为了全面、客观地评估学生在最短路径算法学习过程中的表现，将采用以下评估方式：1.平时表现：观察学生在课堂上的参与程度、提问回答和小组讨论的表现，以了解学生的学习态度和理解程度。
最短路径教案最短路径是图论中的一个重要概念，指的是在图中找到两个顶点之间最短的路径。
最短路径算法有很多种，本教案将重点介绍迪杰斯特拉算法。
一、教学目标学生能够理解最短路径的概念以及其在实际生活中的应用学生能够掌握迪杰斯特拉算法的基本原理和实现方法学生能够独立运用迪杰斯特拉算法解决最短路径问题二、教学内容最短路径的概念介绍迪杰斯特拉算法的基本原理和实现方法迪杰斯特拉算法的应用案例分析三、教学步骤步骤一：引入概念通过实际例子引出最短路径的概念，如在城市中从起点到终点的最短路径，或者在地图上找到两个地点之间的最短路径。
步骤二：迪杰斯特拉算法的原理介绍通过图示和文字解释迪杰斯特拉算法的原理，即不断更新顶点的距离值，直到找到最短路径。
步骤三：迪杰斯特拉算法的实现方法介绍迪杰斯特拉算法的具体实现方法，包括数据结构的选择和算法的实现过程。
可以通过伪代码的形式进行讲解。
步骤四：迪杰斯特拉算法的应用案例分析通过实际案例的分析，如网络路由、航班路径规划等，展示迪杰斯特拉算法的应用场景和解决方法。
步骤五：课堂练习组织学生进行课堂练习，让学生独立运用迪杰斯特拉算法解决最短路径问题。
可以选择一些简单的图来进行实践。
步骤六：总结总结迪杰斯特拉算法的基本原理和实现方法，回顾最短路径的概念，在实际生活中的应用。
四、教学手段通过图示、文字和实例相结合的方式，让学生更直观地理解最短路径的概念和迪杰斯特拉算法的原理。
通过讲解、演示和实践相结合的方式，让学生掌握迪杰斯特拉算法的实现方法和应用技巧。
五、教学评价课堂上进行小组讨论和问题解答，检查学生对最短路径和迪杰斯特拉算法的掌握程度。
课后布置一些编程练习，让学生运用迪杰斯特拉算法解决最短路径问题，检查学生独立运用算法的能力。
c课程设计最短路径一、教学目标本节课的教学目标是让学生掌握最短路径算法的基本原理和实现方法。
知识目标包括了解最短路径问题的背景和意义，理解迪杰斯特拉算法和贝尔曼-福特算法的原理，掌握这两种算法的实现和优化方法。
技能目标包括能够运用迪杰斯特拉算法和贝尔曼-福特算法解决实际问题，能够编写相应的程序实现最短路径算法。
情感态度价值观目标包括培养学生的逻辑思维能力，提高学生解决实际问题的能力，激发学生对计算机科学和算法的兴趣。
二、教学内容本节课的教学内容主要包括最短路径问题的定义和意义，迪杰斯特拉算法和贝尔曼-福特算法的原理和实现，以及最短路径算法的应用。
首先，介绍最短路径问题的背景和意义，引导学生了解最短路径问题在实际中的应用。
然后，讲解迪杰斯特拉算法和贝尔曼-福特算法的原理，通过示例让学生理解这两种算法的实现方法。
最后，介绍最短路径算法的应用，让学生了解如何运用这两种算法解决实际问题。
三、教学方法为了达到本节课的教学目标，将采用多种教学方法相结合的方式进行教学。
首先，采用讲授法，向学生讲解最短路径问题的定义和意义，以及迪杰斯特拉算法和贝尔曼-福特算法的原理和实现方法。
然后，采用案例分析法，通过具体的例子让学生理解这两种算法的应用。
接着，采用讨论法，让学生分组讨论并解决实际问题，培养学生的逻辑思维能力和团队合作能力。
最后，采用实验法，让学生编写程序实现最短路径算法，提高学生的动手能力和实际问题解决能力。
四、教学资源为了支持本节课的教学内容和教学方法的实施，将准备多种教学资源。
教材方面，选择《数据结构与算法》一书，作为学生学习的参考。
参考书方面，推荐学生阅读《算法导论》一书，以深入了解算法的原理和实现。
多媒体资料方面，制作PPT课件，通过图形和动画等方式直观地展示最短路径问题的实例和算法的实现过程。
实验设备方面，准备计算机和网络设备，让学生能够编写程序并实际运行最短路径算法。
五、教学评估本节课的评估方式将包括平时表现、作业和考试三个部分。
数据结构最短路径课程设计一、课程目标知识目标：1. 理解图的基本概念，掌握图的表示方法及其特性；2. 掌握最短路径的两种经典算法：Dijkstra算法和Floyd算法；3. 能够运用所学算法解决实际生活中的最短路径问题。
技能目标：1. 能够运用数据结构中的图，进行实际问题的建模；2. 能够编写并实现Dijkstra算法和Floyd算法，解决最短路径问题；3. 能够通过分析、比较两种算法，选择合适的算法解决特定问题。
情感态度价值观目标：1. 培养学生面对复杂数据结构问题时，保持积极探究、解决问题的态度；2. 培养学生的团队协作能力，学会在团队中分享、交流、互助；3. 通过解决实际生活中的问题，培养学生将所学知识应用于实践的意识。
课程性质分析：本课程为数据结构中的图部分，以最短路径为具体实例，帮助学生理解图的概念及其在实际中的应用。
学生特点分析：学生已具备一定的编程能力和数据结构基础知识，但对图的相关概念和算法掌握不足，需要通过具体案例和实际操作，提高理解和应用能力。
教学要求：1. 以实际问题引入，激发学生的学习兴趣；2. 采用任务驱动法，引导学生自主探究、实践；3. 结合课堂讲解和实际操作，使学生在实践中掌握知识；4. 注重团队合作，培养学生的沟通与协作能力。
二、教学内容1. 图的基本概念：图的定义、图的表示方法（邻接矩阵、邻接表）、图的遍历（深度优先搜索、广度优先搜索）。
2. 最短路径问题：最短路径的定义、最短路径算法的应用场景。
3. Dijkstra算法：算法原理、算法步骤、实例分析、编程实现。
4. Floyd算法：算法原理、算法步骤、实例分析、编程实现。
5. 算法比较与分析：Dijkstra算法与Floyd算法的优缺点比较、适用场景分析。
6. 实践项目：设计一个实际场景的最短路径问题，要求学生运用所学算法进行解决。
教学内容安排与进度：第一课时：图的基本概念、图的表示方法、图的遍历。
第二课时：最短路径问题、Dijkstra算法原理与实例分析。
沈阳大学
课程设计报告
课程设计名称：数据结构课程设计课程设计题目：最短路径算法
院（系）：信息工程学院
专业：通信工程专业
班级：12级通信2班
学号：F1258212
姓名：刘维成
指导教师：
目录
1 课程设计介绍 (1)
1.1课程设计内容 (1)
1.2课程设计要求 (1)
2 课程设计原理 (2)
2.1课设题目粗略分析 (2)
2.2原理图介绍 (3)
2.2.1 功能模块图 (3)
2.2.2 流程图分析 (3)
3 数据结构分析 (8)
3.1存储结构 (8)
3.2算法描述 (8)
4 调试与分析 (9)
4.1调试过程 (9)
4.2程序执行过程 (9)
参考文献 (11)
附录（关键部分程序清单） (12)
1 课程设计介绍
1.1 课程设计内容
设计程序，实现最短路径的求法，系统主要功能如下：
1.编写算法能够建立带权图，并能够用Dijkstra算法求该图的最短路径。
2.能够选择图上的任意一顶点做为开始节点。
最短路径输出不必采用图形方式，可顶点序列方式输出。
1.2 课程设计要求
1.带权图的顶点信息用字符串，数据可自定。
2.参考相应的资料，独立完成课程设计任务。
3.较规范课程设计报告和软件代码。
2 课程设计原理
2.1 课设题目粗略分析
根据课设题目要求，拟将整体程序分为三大模块。
两个子模块相互独立，没有嵌套调用的情况，在主模块中调用上面两个子模块以下是三个模块的大体分析：
1.建立有向图的存储结构.
2.应用Dijkstra算法求出该有向图的最短路径。
3.在主函数中调用上面两个子函数，完成求最短路径的程序设计。
4.
2.2 原理图介绍
2.2.1 功能模块图
图2.1 功能模块图 2.2.2 流程图分析
1. 主函数
2.2主函数流程图
2. Create 函数
2.3Create函数流程图
3.Dijkstra函数
2.4Dijkstra函数流程图
3 数据结构分析
3.1 存储结构
一个图的邻接矩阵表示是唯一的。
图的邻接矩阵表示，除了需要用一个二维数组存储顶点之间相邻关系的邻接矩阵外，通常还需要使用一个具有n个元素的一维数组存储顶点信息，其中下标为i的元素存储顶点vi的信息。
因此，图的邻接矩阵的存储结构定义如下:
#define MVNum 50
typedef struct {
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum]；
}Mgraph;
3.2 算法描述
1. Dijkstra算法核心是贪心，实质是按路径长度递增产生诸顶点的最短路径算法。
迪杰斯特拉算法可用自然语言描述如下：
初始化S和D,置空最短路径终点集，置初始的最短路径值；
S[v1]=TRUE;D[v1]=0;
While(S集中的顶点数<n)
{
开始循环，每次求的v1到某个v顶点的最短路径，并将v加到S集中;
S[v]=TRUE; 更新当前最短路径及距离。
}
2Dijkstra算法结束后，通过设置一个数组记录下一个节点的前趋节点，然后通过倒叙的方式输出该最短路径。
4 调试与分析
4.1 调试过程
在调试程序是主要遇到一下几类问题：
1.程序完成后，调试时没有发现问题，但是当输入开始节点后，运行框却不停的
出现”<-a”,后来重新检查程序时发现for循环的括号后面多了一个”;”，去掉该分号之后，程序可以运行。
2.程序可以运行，但是输出结果不是有序的，解决方法，设立一个前驱数组，用
以记录节点的双亲节点，然后按照倒叙的方式读出该条最短路径的有向序列。
4.2程序执行过程
4.1程序执行过程
4.2程序执行过程
参考文献
[1] 《数据结构》（用面向对象方法与C++描述），殷人昆等，清华大学出版社， 2010年3月。
[2] 《算法与数据结构习题精解和实验指导》，宁正元等，清华大学出版社，
2009年6月。
[3] 《数据结构课程设计》，苏仕华等，机械工业出版社，2010年3月。
[4]《C程序设计》，谭浩强编，清华大学出版社，2006年6月。
附录（关键部分程序清单）程序代码
#include<stdio.h>
#include<stdlib.h>
#define MVNum 100
#define Maxint 32767
typedef char VertexType;
typedef int Adjmatrix;
typedef enum {FALSE,TRUE}boolean;
typedef struct {
VertexType vexs[MVNum];
Adjmatrix arcs[MVNum][MVNum];
}MGraph;
int D1[MVNum],P1[MVNum];
int D[MVNum][MVNum],P[MVNum][MVNum];
void CreateMGraph(MGraph *G,int n,int e)
{
int i,j,k,w;
char a,b;
for(i=1;i<=n;i++)
G->vexs[i]=i;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
G->arcs[i][j]=Maxint;
printf("输入%d条边的i,j及w:\n",e);
for(k=1;k<=e;k++)
{
fflush(stdin);
scanf("%c,%c,%d",&a,&b,&w);
i=a-'a'+1;
j=b-'a'+1;
G->arcs[i][j]=w;
}
printf("有向图的存储结构建立完毕!\n");
}
void Dijkstra(MGraph G,int v1,int n)
{
int D2[MVNum],P2[MVNum];
int v,i,w,min;
boolean S[MVNum];
for(v=1;v<=n;v++)
{
S[v]=FALSE;
D2[v]=G.arcs[v1][v];
if(D2[v]<Maxint)
P2[v]=v1;
else
P2[v]=0;
}
D2[v1]=0;S[v1]=TRUE;
for(i=2;i<=n;i++)
{
min=Maxint;
for(w=1;w<=n;w++)
if(!S[w]&&D2[w]<min)
{
v=w;min=D2[w];
}
S[v]=TRUE;
for(w=1;w<=n;w++)
if(!S[w]&&(D2[v]+G.arcs[v][w]<D2[w]))
{
D2[w]=D2[v]+G.arcs[v][w];
P2[w]=v;
}
}
printf("路径长度路径\n");
for(i=1;i<=n;i++)
{
printf("%5d",D2[i]);
printf("%5c",i-1+'a');v=P2[i];
while(v!=0)
{
printf("<-%c",v-1+'a');
v=P2[v];
}
printf("\n");
}
}
void main()
{
MGraph G;
int n,e,v;
char ch;
printf("输入图中顶点个数和边数n,e:");
scanf("%d,%d",&n,&e);
CreateMGraph(&G,n,e);
while(1)
{
printf("求最短路径，输入开始点v:");
fflush(stdin);
scanf("%c",&ch);
v=ch-'a'+1;
Dijkstra(G,v,n);
}
}
沈阳航空航天大学课程设计报告。
