摘 要
根据普里姆算法和迪杰斯特拉算法,编写C++程序对该街道居民的路径选取过程进行模拟。所得结论显示问题解答结果与分析的结论相吻合,从而得出最佳线路铺设方案,并成功解决服务设施点选址问题。
关键词:邻接矩阵;普里姆算法;迪杰斯特拉算法;最短路径;最小生成树。
Abstract
This article has resolved a network optimization problem which has an weight. Uniting the knowledge in the diagram theory, we analyze the problem comprehensively, and adopt one dimension array and adjacency matrix to store the number of the residents resided in this section and the distance between two different sections. By quantitatively analyzing question one, we change the problem of the paving connection scheme into constructing the Minimum Cost Spanning Tree for connected network, and make Prim algorithm to answer the question; By quantitatively analyzing question two, we change the choosing address issue of service establishment into answering the shortest path for other verticals, we make Dijkstra algorithm to answer this question.
Based on Prim algorithm and Dijkstra algorithm, we simulate the choosing path process of this street by C++ program. The result shows that: the result of trouble shooting same to the analyzing result, and we succeed to answer the choosing address issue of service establishment.
Keywords: adjacency matrix; Prim algorithm; Dijkstra algorithm; The most short-circuit path; Minimal spanning tree.