Privacy is an important keyword in today’s social era. Information has to be shared on the social web without compromising on the sensitive information relating to a user. Major research studies have been done to generalize or suppress the sensitive information such that identity is masked or unknown to others. However, there is always a compromise in the utility of the data. Some research work is also carried on the shortest path privacy preservation which holds the sensitive data. Here the shortest path/multiple paths are masked and this data is released to the third party. In this paper, we discuss a technique with edge modification and edge swap technique on the shortest path. Since this method does not involve the deletion of edges or major link changes the utility of the released data is more. The result of this approach shows a significant increase in masking sensitive data and is also applicable to weighted undirected graphs. © 2018, Institute of Advanced Scientific Research, Inc.. All rights reserved.