I am using dijkstra by adding a reverse edge of weight 1. Answer will be MIN ( Shortest distance, total_edges - shortest_distance);