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  | 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
How to Cite this Article?
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
How to Share this Article?
Similar Articles with Keyword 'Graph'
A Study on Graph with Desmos through ICT in Diploma in Elementary Education of Tamil Nadu State Board
P. Charles Paul | G. Thulasi 
Chromatic Number and Weak Complement of L-Fuzzy Graphs
Sreedevi V.S. | Dr. Bloomy Joseph