Approximate shortest distance query is the basic pattern of graph search.The graph data is usually encrypted in order to protect the security of the outsourced data.The existing encryption schemes use the two-hop labeling model to construct the encryption index,which leads to the high-complexity of index structure and the reduction of query efficiency.This paper proposed an algorithm based on graph compression,which can improve the efficiency of the graph query and support the approximate shortest distance query of encrypted graph.The algorithm uses K-mediods clustering so that the nodes in the graph are divided into K clusters according to the distance.The nodes in each cluster use their central node as agent node.When querying the shortest distance between two points,the point in different clusters uses the proxy node to query distance.The experimental results show that the algorithm can effectively reduce the query time and improve the query efficiency,and the deviation rate of the query result is acceptable.