# International Journal of Science and Research (IJSR)Since Year 2012 | Open Access | Fully Refereed | Peer Reviewed

Research Paper | Mathematics | Iraq | Volume 4 Issue 7, July 2015

## An Approach for Solving Transportation Problem Using Modified Kruskal's Algorithm

Kadhim B. S. Aljanabi [2] | Anwar Nsaif Jasim

Abstract: This paper presents a new approach for finding a minimum feasible solution for transportation problem with different types (balanced and unbalanced). The approach is based mainly on using graph theory in general and Kruskals algorithm for finding Minimum Spanning Tree (MST) in finding out the first minimum cost between sources and demands. All the edges between sources and demands are sorted in an ascending order according to the weights (costs of unit delivery between sources and demands) in an array. Starting from the first element of the array which represents the absolute minimum cost, then delete either the source vertex with all its outgoing edges if this source is satisfied or deleting the targeted demand with all its incoming edges if this demand is satisfied or even both. Different examples are considered in this paper to study the correctness and the scalability of the proposed approach. The examples cover both balanced and unbalanced transportation models. As Kruskals algorithm works with O (E log V) time complexity, where E represents the number of edges and V is the number of vertices, however, the proposed approach tends to reduce the number of vertices and the edges after each iteration and hence it will converge faster.

Keywords: Graph, Algorithms, Transportation Problem, Kruskals algorithm, MST

Edition: Volume 4 Issue 7, July 2015,

Pages: 2426 - 2429

Kadhim B. S. Aljanabi, Anwar Nsaif Jasim, "An Approach for Solving Transportation Problem Using Modified Kruskal's Algorithm", International Journal of Science and Research (IJSR), Volume 4 Issue 7, July 2015, pp. 2426-2429, https://www.ijsr.net/get_abstract.php?paper_id=SUB157010

#### Similar Articles with Keyword 'Graph'

Research Paper, Mathematics, India, Volume 6 Issue 11, November 2017

Pages: 1792 - 1796

### A Study on Graph with Desmos through ICT in Diploma in Elementary Education of Tamil Nadu State Board

P. Charles Paul | G. Thulasi [2]