PENERAPAN ALGORITMA DIJKSTRA UNTUK MENENTUKAN JALUR TERPENDEK PADA PENDISTRIBUSIAN BARANG (STUDI KASUS : PT. SNS (GARUDA FOOD) CABANG PALU)

Traveling Salesman Problem (TSP) is a problem of Optimization, which aims to visit each place from the set of places specified once and only once then return to the original place at the end of the route with a minimum distance, time, and cost. The process of distributing goods that has been carried out by PT. SNS (Garuda Food) Palu Branch has not been well planned because the determination of the distribution route of goods carried out is only limited to guessing which results in an erratic distribution path so that the distribution route is still quite long, therefore a proper plan is needed in determining the distribution path of goods so that the distance traveled is more minimum. The solution used to solve the problem in this study is to use dijkstra algorithm that works using the greedy principle, each step is selected based on the value of the closest distance and then connects the selected node by comparing the distance values from each point so that it can find an efficient path. Data obtained for the search of this distribution route from the office of PT. SNS (Garuda Food) Palu Branch with 20 points, 57 sides and a distribution mileage traversed by 19,200 m. Dijkstra's algorithm can easily determine the shortest path on the distribution of goods proven to be able to produce the closest travel path of 18,000 m which can save the distribution mileage of 1,200 m and the results obtained are very accurate.

Keywords: Traveling Salesman Problem (TSP), Shortest Path, Dijkstra Algorithm, PT. SNS (Garuda Food) Palu Branch