• AJ Tamber
  Mathematics Department, Benue State University Makurdi, Benue State, Nigeria
  




• FO Ikpotokin
  Computer Science Department, Ambrose Alli University, Ekpoma, Edo State, Nigeria
  




• LU Okafor
  Mathematics Department, Nigerian Defense Academy Kaduna, Kaduna State Nigeria
  

The research work is aimed at finding the optimal graph of the Travel Salesman Problem of the vehicular movement from multiple sources of the Nigeria roads network of the coastal towns: Lagos, Port Harcourt, Asaba and Calabar through the hinterland to multiple destinations (border towns) of Katsina, Sokoto and Maiduguri so as to minimize the cost of fueling, maintenance and loss customers and goods/services get delivered to destinations in good time. In obtaining the optimal graph, the Kruskal algorithm of the minimum spinning tree was used and was implemented by a computer application package, TORA, developed by Taha. The optimal minimum spinning graph is: Lagos – Abeokuta – Ibadan – Osogbo – Ilorin – Osogbo – Akure - Ado Ekiti – Akure – Benni – Asaba – Owerri - Port Harcourt – Umuahia – Uyo – Calabar – Uyo – Umuahia - Port Harcourt – Owerri – Asaba – Benni – Awka – Enugu – Abakelike – Enugu – Awka – Benni – Akure – Lokoja – Abuja – Minna –Abuja – Kaduna – Kano – Katsina - Kano – Dutse – Kano – Gasua – Sokoto – Brini Kebbi – Sokoto – Gusau – Kano – Kaduna - Abuja – Lafia – Makurdi – Lafia – Jos – Bauchi – Gombe – Yola – Jalingo – Yola – Gombe – Damaturu – Maiduguri with the total distance of 8327Km.