Abstract: This study deals with the problem of finding shortest paths in traversing some locations within the Sokoto metropolis. In particular, It explores the use of Dijkstra’s algorithm in constructing the minimum spanning tree considering the dual carriage ways in the road network of Sokoto metropolis. The results shows a remarkable reduction in the actual distances as compared with the ordinary routing. These results indicate, clearly the importance of this type of algorithms in the optimization of network flows.