Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm
Shortest path algorithms have been long applied to solve daily problems by selecting the most feasible route with minimum cost or time. However, some of the problems are not simple. This study applied the case using Dijkstra's algorithm on a graph representing street routes with two possible di...
Main Authors: | , |
---|---|
Format: | Article |
Language: | English |
Published: |
Bina Nusantara University
2016-09-01
|
Series: | ComTech |
Subjects: | |
Online Access: | https://journal.binus.ac.id/index.php/comtech/article/view/2534 |
_version_ | 1797714601053257728 |
---|---|
author | Elizabeth Nurmiyati Tamatjita Aditya Wikan Mahastama |
author_facet | Elizabeth Nurmiyati Tamatjita Aditya Wikan Mahastama |
author_sort | Elizabeth Nurmiyati Tamatjita |
collection | DOAJ |
description | Shortest path algorithms have been long applied to solve daily problems by selecting the most feasible route with minimum cost or time. However, some of the problems are not simple. This study applied the case using Dijkstra's algorithm on a graph representing street routes with two possible digraphs: one-way and twoway. Each cost was able to be changed anytime, representing the change in traffic condition. Results show that the usage of one way digraph in mapping the route does make the goal possible to reach, while the usage of twoway digraph may cause confusion although it is probably the possible choice in the real world. Both experiments showed that there are no additional computation stresses in re-calculating the shortest path while going halfway to reach the goal. |
first_indexed | 2024-03-12T07:54:22Z |
format | Article |
id | doaj.art-dc41e0f818f44d649c14b83594c2c3ea |
institution | Directory Open Access Journal |
issn | 2087-1244 2476-907X |
language | English |
last_indexed | 2024-03-12T07:54:22Z |
publishDate | 2016-09-01 |
publisher | Bina Nusantara University |
record_format | Article |
series | ComTech |
spelling | doaj.art-dc41e0f818f44d649c14b83594c2c3ea2023-09-02T20:23:27ZengBina Nusantara UniversityComTech2087-12442476-907X2016-09-017316117110.21512/comtech.v7i3.25341957Shortest Path with Dynamic Weight Implementation using Dijkstra’s AlgorithmElizabeth Nurmiyati Tamatjita0Aditya Wikan Mahastama1Sekolah Tinggi Teknologi AdisutjiptoUniversitas Kristen Duta WacanaShortest path algorithms have been long applied to solve daily problems by selecting the most feasible route with minimum cost or time. However, some of the problems are not simple. This study applied the case using Dijkstra's algorithm on a graph representing street routes with two possible digraphs: one-way and twoway. Each cost was able to be changed anytime, representing the change in traffic condition. Results show that the usage of one way digraph in mapping the route does make the goal possible to reach, while the usage of twoway digraph may cause confusion although it is probably the possible choice in the real world. Both experiments showed that there are no additional computation stresses in re-calculating the shortest path while going halfway to reach the goal.https://journal.binus.ac.id/index.php/comtech/article/view/2534shortest path, dynamic weight, Dijkstra’s algorithm, graph, digraph |
spellingShingle | Elizabeth Nurmiyati Tamatjita Aditya Wikan Mahastama Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm ComTech shortest path, dynamic weight, Dijkstra’s algorithm, graph, digraph |
title | Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm |
title_full | Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm |
title_fullStr | Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm |
title_full_unstemmed | Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm |
title_short | Shortest Path with Dynamic Weight Implementation using Dijkstra’s Algorithm |
title_sort | shortest path with dynamic weight implementation using dijkstra s algorithm |
topic | shortest path, dynamic weight, Dijkstra’s algorithm, graph, digraph |
url | https://journal.binus.ac.id/index.php/comtech/article/view/2534 |
work_keys_str_mv | AT elizabethnurmiyatitamatjita shortestpathwithdynamicweightimplementationusingdijkstrasalgorithm AT adityawikanmahastama shortestpathwithdynamicweightimplementationusingdijkstrasalgorithm |