在临潼校园里,有若干个交叉路口(节点)和连接这些路口的道路(边)。现在需要设计一个公共交通路线,以方便学生在校园内出行。为了提高交通效率,需要找到一个最小生成树,以及根据最小生成树和单源最短路径算法设计公共交通路线图和站点。
要求:
使用Prim算法找到校园内的最小生成树使用 Dijkstra 算法找到从指定的出发点到其他各个节点的最短路径根据最小生成树和最短路径信息,设计一个公共交通路线图,包括站点和路线. 最后呈现的效果:输入:
交叉路口(节点)的个数和位置坐标。道路(边)的连接关系和长度。
公共交通的出发点。
输出:
最小生成树的边集合。
从指定出发点到其他各个节点的最短路径。公共交通路线图,包括站点和路线。