International Journal of Science and Research (IJSR)

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

ISSN: 2319-7064




Downloads: 137

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


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?

Enter Your Email Address




Similar Articles with Keyword 'Graph'

Downloads: 150 | Weekly Hits: ⮙1 | Monthly Hits: ⮙1

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]

Share this Article

Downloads: 131

Research Paper, Mathematics, India, Volume 9 Issue 2, February 2020

Pages: 687 - 690

Chromatic Number and Weak Complement of L-Fuzzy Graphs

Sreedevi V.S. | Dr. Bloomy Joseph [3]

Share this Article


Top