Help needed with Brute force to find the best path in a Graph

[Zaad]

Hi;
I have a problem which involves the road map of a certain country is given and I have to find the best solution to find a best solution for the map by demolishing the extra roads in the map and keep the roads that would make it possible for the travelling between the cities in the shortest distance with the condition that road between X and Y is essential to be retained. I have done this by using the minimum spanning tree algorithms and the Dijkstras algorithm but I am also required to find a solution to it by making use of the brute force method and compare the efficiency of the algorithm. I made searches in the google regarding the problem and I got only the hamiltonian circuit problem regarding the graphs with brute force. Can some one at least provide me with the pseudo code of the Brute Force implementation as it is no where to be found.... Thank you in advance