We address in this paper the connected pp-median problem on complete multi-layered graphs. We first solve the corresponding 1-median problem on the underlying graph in linear time based on the structure of the induced path. For p≥2, we prove that the connected pp-median contains at least one vertex in the layered set corresponding to the 1-median or its adjacent vertices in the induced path. Then, we develop an O(nlogn) algorithm that solves the problem on a complete multi-layered graph with nn vertices.