Network planning is of key importance during the construction of new communities and cities, in which telephone and data services have to be introduced as a component of the overall master plan of the city. The system accepts the map of a city in the form of its streets and intersection nodes coordinates, the specifications of the available cable sizes, and the cost information for the cables. The system determines the minimum cost network that satisfies the demand and constraints. The problem is treated as a clustering around medoids problem where the distances are represented by weighted shortest paths. In this paper, the Partitioning Around Medoids (PAM) original algorithm have been modified. Results demonstrate the effectiveness and flexibility of the modifying algorithm in tackling the important problem of rural network planning. Comparisons with related work are presented showing the advantages of the CWSP-PAM (Clustering with Shortest Path-PAM) algorithm introduced in this paper.