This article presents a novel method for computing distances between hosts in a computational Grid. Our method allows to represent the cost to achieve any operation involving some services in a Grid environment. We demonstrate why the current monitoring tools are not sufficient in grid environments that lack high level tools to combine several sources of monitoring while taking into account particular constraints for some given applications. We show how this method has been embedded in a Grid service, namely the Network Distance Service (NDS). We illustrate the benefit of our approach in terms of accuracy, using an algorithm from graph theory on a grid planning scenario. We explain some implementation issues and discuss how the proposed NDS service can be useful to any grid service who needs some accurate evaluation for a decision making process involving such distances.