【问题描述】 有一个快递小哥,准备所辖区域的n 个点派送快递,设这 n 个点间两两都有道路通行,小哥从某一派送点出发只需要走n-1条道路就可以走完n个点,但由于路况差异,每条道路所需的时间不同。选择最佳的送货路径使总路径时间最短,这个问题即为求网的“最小生成树”。 【基本要求】 网采用邻接矩阵为存储结构,以顶点对(i,j)的形式输出最小生成树的边。 【测试数据】 自行设计。 【实现提示】 可选用Kruskal 算法或Prim 算法来求网的最小生成树,无论哪一个算法都要选好恰当 的辅助数据结构,以存放边或顶点的集合。
2021-11-26 19:13:07
4KB
最佳路径选择
1