Analysis and Understanding of Dijkstra Algorithm

Oct 13, 2025 by miodeya.com 99 views

Introduction

Determining the shortest path from one place to another is a challenge that is often faced in everyday life. With the increasing number of tourist attractions and the growing number of visitors, finding the most efficient route to visit these attractions has become a crucial task. In this study, we will explore the implementation of the Dijkstra algorithm in searching for the shortest route of the tourist attractions in the city of Medan.

Background of the Study

The city of Medan is a popular tourist destination in Indonesia, known for its rich cultural heritage and natural beauty. The city has a wide range of tourist attractions, including Merdeka Square, Old City, Medan Grand Mosque, Maimun Palace, Rahmat Gallery, Wonder Water World, Cadika Tourism Park, Medan Zoo, Hairos Waterpark, Graha Annai Velangkanni, Asam Kumbang Pamatment Park, and Area Building. However, with the increasing number of visitors, finding the most efficient route to visit these attractions has become a challenge.

Methodology

In this study, we used the Dijkstra algorithm to calculate the shortest pathway that can be reached to visit all the tourist attractions in Medan. The Dijkstra algorithm is an effective solution to find the shortest path between one point to another in a graph that has a positive weight. The algorithm works by expanding the path from the starting point to the destination point gradually, ensuring that each step taken is the shortest that may reach the goal.

Analysis and Understanding of Dijkstra Algorithm

The Dijkstra algorithm was first introduced by Edsger Dijkstra in 1956 and became one of the most widely used algorithms for the shortest path search problem in the graph. The work process of this algorithm is to expand the path from the starting point to the destination point gradually, ensuring that each step taken is the shortest that may reach the goal.

Initialization

The first step in the Dijkstra algorithm is to initialize the distance from the starting point (vertex) to all other vertex in the graph. This distance is regulated to infinity (∞), except for the distance to the initial vertex that is set 0.

Select the Nearest Vertex

From the Vertex list, choose Vertex with the smallest distance that has not been marked as "visited".

Update Distance

Update the distance to the neighbor's vertex from the nearest Vertex that has just been selected by adding the edge weight that connects it. If the new distance is smaller than the previous distance, update the distance.

Mark Vertex

Mark Vertex that has been visited.

Repeat the Process

Repeat steps 2-4 until all vertex has been visited or until the shortest distance to vertex has been found.

Implementation of Dijkstra Algorithm in Medan

In this study, we applied the Dijkstra algorithm to find the shortest pathway that can be reached to visit all the tourist attractions in Medan. The result of the application of the Dijkstra algorithm shows the optimal pathway that is the v1-V2-V4-V3-V12-V6-V5-V12-V10-V10-V8-V8-V7 with a total length of about 46.9 km.

Conclusion

The implementation of the Dijkstra algorithm in searching the shortest route in Medan is very beneficial for tourists who want to explore various tourist attractions efficiently. By understanding this method, visitors can plan their visit better, avoid traffic jams, and enjoy each location more optimally. In addition, the analysis produced by this algorithm provides useful information for map application developers and transportation services to improve the quality of service and user experience.

Recommendations

Based on the result of this study, we recommend that:

Tourists use the Dijkstra algorithm to plan their visit to Medan and explore various tourist attractions efficiently.
Map application developers and transportation services use the analysis produced by the Dijkstra algorithm to improve the quality of service and user experience.
Local governments and tourist attractions use the result of this study to improve services and accessibility to these tourist attractions.

Limitations of the Study

This study has several limitations, including:

The study only focused on the tourist attractions in Medan and did not consider other factors that may affect the shortest route, such as traffic congestion and road conditions.
The study used a simplified model of the graph and did not consider the complexity of the real-world graph.
The study did not consider the dynamic nature of the graph and the changing weights of the edges.

Future Research Directions

Future research directions include:

Developing a more complex model of the graph that considers the dynamic nature of the graph and the changing weights of the edges.
Considering other factors that may affect the shortest route, such as traffic congestion and road conditions.
Applying the Dijkstra algorithm to other cities and tourist attractions to compare the results and identify the best practices.

References

Dijkstra, E. W. (1956). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Kleinberg, J. (2006). Algorithm design. Addison-Wesley.

Appendix

The appendix includes the detailed calculation of the Dijkstra algorithm and the result of the application of the algorithm to find the shortest pathway that can be reached to visit all the tourist attractions in Medan.

Q: What is the Dijkstra algorithm?

A: The Dijkstra algorithm is a well-known algorithm in graph theory that is used to find the shortest path between two nodes in a graph. It was first introduced by Edsger Dijkstra in 1956 and has since become one of the most widely used algorithms for the shortest path search problem in the graph.

Q: How does the Dijkstra algorithm work?

A: The Dijkstra algorithm works by expanding the path from the starting point to the destination point gradually, ensuring that each step taken is the shortest that may reach the goal. The algorithm starts by initializing the distance from the starting point (vertex) to all other vertex in the graph, and then iteratively selects the vertex with the smallest distance that has not been marked as "visited" and updates the distance to the neighbor's vertex.

Q: What are the advantages of using the Dijkstra algorithm?

A: The Dijkstra algorithm has several advantages, including:

It is efficient and can handle large graphs.
It can find the shortest path between two nodes in a graph.
It can be used to find the shortest path in a graph with positive weights.
It can be used to find the shortest path in a graph with negative weights.

Q: What are the limitations of the Dijkstra algorithm?

A: The Dijkstra algorithm has several limitations, including:

It is not suitable for graphs with negative weights.
It is not suitable for graphs with cycles.
It is not suitable for graphs with non-integer weights.

Q: How can the Dijkstra algorithm be used in real-world applications?

A: The Dijkstra algorithm can be used in a variety of real-world applications, including:

Route planning: The Dijkstra algorithm can be used to find the shortest route between two points on a map.
Network optimization: The Dijkstra algorithm can be used to optimize network flows and find the shortest path between two nodes in a network.
Logistics: The Dijkstra algorithm can be used to optimize logistics and find the shortest path between two nodes in a logistics network.

Q: What are the benefits of using the Dijkstra algorithm in the city of Medan?

A: The Dijkstra algorithm can be used to find the shortest path between two points in the city of Medan, which can be beneficial for tourists and locals alike. It can help to reduce travel time and improve the overall efficiency of transportation in the city.

Q: How can the Dijkstra algorithm be used to improve the quality of service and user experience in the city of Medan?

A: The Dijkstra algorithm can be used to improve the quality of service and user experience in the city of Medan by:

Providing accurate and efficient route planning.
Reducing travel time and improving the overall efficiency of transportation.
Improving the user experience by providing real-time information and updates.

Q: What are the future research directions for the Dijkstra algorithm?

A: Some future research directions for the Dijkstra algorithm include:

Developing a more complex model of the graph that considers the dynamic nature of the graph and the changing weights of the edges.
Considering other factors that may affect the shortest route, such as traffic congestion and road conditions.
Applying the Dijkstra algorithm to other cities and tourist attractions to compare the results and identify the best practices.

Q: What are the references for the Dijkstra algorithm?

A: Some references for the Dijkstra algorithm include:

Dijkstra, E. W. (1956). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269-271.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms (3rd ed.). MIT Press.
Kleinberg, J. (2006). Algorithm design. Addison-Wesley.

Q: What are the appendices for the Dijkstra algorithm?

A: The appendices for the Dijkstra algorithm include:

The detailed calculation of the Dijkstra algorithm.
The result of the application of the algorithm to find the shortest pathway that can be reached to visit all the tourist attractions in Medan.