图及其应用.docx

1、任务描述 1.任务：设计一个城市交通咨询模拟系统，利用该系统实现至少两种最优决策：最短路程到达、最省时到达等线路规划。 2．内容： 用户驾车出行由于出行目的的不同对道路路线选择的要求也有不同。例如，有的希望在途中的路程尽可能短，有的则可能希望路程中时间最短。为了能满足广大旅客的需求，编制一个城市交通咨询模拟系统，选取城市部分位置、道路抽象为程序所需要图的顶点和边，并以城市道路长度（路程），道路的某时段的速度等信息作为图结点中的弧信息，为旅客提供这两种最优决策的交通咨询。 2、主要数据类型与变量 #define inf 99999999 #define max_element 50 typ 在这个实验中，主要涉及到的知识点是图数据结构和算法，特别是如何使用图来解决实际问题，如城市交通咨询系统的线路规划。以下是对这些知识点的详细解释： 1. 图数据结构：图是由顶点（节点）和边（连接顶点的线）构成的数据结构，它可以用来表示对象之间的关系。在本实验中，城市中的位置被抽象为顶点，道路作为连接这些顶点的边。每条边可以带有权值，如道路长度和速度，这些信息对于计算最短路程和最省时到达至关重要。 2. 最短路径问题：实验中提到了两种最优决策——最短路程到达和最省时到达。这是图论中的经典问题，通常可以通过Dijkstra算法或者Floyd-Warshall算法来解决。在本例中，Floyd算法被用来计算这两类问题。Floyd-Warshall算法是一个动态规划方法，用于查找图中所有顶点之间的最短路径。 3. Floyd-Warshall算法：这是一个用于解决所有对最短路径问题的算法，它通过迭代的方式逐步更新所有可能的路径，直到找到最短路径。在实验中，有两个版本的Floyd算法，一个是`Floyd_dist`，用于计算最短距离，另一个是`Floyd_time`，用于计算最短时间。这两个函数都接受一个二维数组`e`（表示边的权重，可能是路程）和`t`（表示速度），以及起始和结束点，来找出两个点之间最短的距离或时间。 4. 数据类型与变量定义：`#define inf 99999999`定义了一个极大的数值，用于表示没有路径或者路径无穷远。`#define max_element 50`定义了数组的最大元素数量。`struct Position`定义了一个坐标结构体，包含横坐标`x`，纵坐标`y`，半径`r`（可能用于绘图）和一个整型变量`i`，具体用途未明确。 5. 图形编程：实验中提到了`easyx`库，这是一个C语言的图形库，用于简化图形绘制。`Draw`和`DrawLine`函数用于画点和线，`Old_Map`和`New_Map`可能是显示不同地图的函数。 6. 实验流程：实验开始时，用户可能通过`Menu`函数选择不同的功能。`Floyd_dist`和`Floyd_time`分别执行最短距离和最短时间的计算，然后可能通过图形界面显示结果。 7. 测试与评估：实验包含了测试方案和结果分析，这有助于验证算法的正确性和效率，以及程序的可用性。 8. 总结与讨论：通过实验，学生不仅掌握了图的处理方法，还深化了对Floyd算法的理解，并学习了使用`easyx`进行图形编程，这对未来的学习和实践具有积极意义。 这个实验项目充分展示了理论知识如何应用于解决实际问题，同时也提供了练习和巩固算法实现以及图形编程技能的机会。