{'fraction_non_alphanumeric': 0.020886650705853216, 'fraction_numerical': 0.010319491455461075, 'mean_word_length': 4.471544715447155, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A shortest path problem for tsunami evacuation in Padang City using Floyd-Warshall algorithm

Padang City is a Capital City of West Sumatera Province bordering on the Indian Ocean and active collision zone of two plates namely Indo-Australian plate and the Eurasian plate. This causes Padang City is very vulnerable to earthquake and tsunami. Therefore, determination of a path of evacuation is very important to do. One of the methods is used Floyd-Warshall Algorithm. The Algorithm will determine the shortest path of tsunami evacuation to be searched for all pairs of vertices of the way. In this research, the problem is how to choose the shortest path of tsunami evacuation at Padang Utara Subdistrict. The results are some of the shortest paths of tsunami evacuation that could pass by people in the district of Padang Utara from the beach area to the nearest shelter.


Introduction
Indonesia lies at the meeting of three major tectonic plates of the world namely Ocean Plate of Indian -Australia, Eurasian Plate and Pacific Ocean Plate. The three plates move relatively press to each other, thus causing territory of Indonesia has a very high earthquake activity. One of the provinces in Indonesia that is very vulnerable to the earthquake is the province of West Sumatra.
Earthquakes occurring on the ocean floor with a magnitude more than 6.0 on the Richter scale and an earthquake center depth of less than 60 km will cause a tsunami. Tsunami comes from the Japanese language Tsu meaning port and nami means wave. In general, tsunamis are the movement of water bodies caused by sudden vertical changes in sea level. One of the areas prone to tsunami waves in West Sumatra is the city of Padang. Padang City is the capital of West Sumatra province located on the coast of Sumatra. Padang City is also directly adjacent to the Indian Ocean and the active collision zone of two plates (Indo-Australian and Eurasian plates) and is adjacent to the fracture of the statue which is often the epicenter of the earthquake.
The sub-districts of Padang City which include the red zone of the tsunami are Koto Tangah, Bungus Teluk Kabung, Padang Selatan, Padang Utara, Padang Timur and Padang Barat. To date there are still many government buildings in Padang city and the West Sumatra provincial government in the red zone of tsunami such as the governor's office, the provincial DPRD building, the office of the tourism office, and others. Included also Pasar Raya Padang which became the center of public crowd Padang City. Based on data from the Central Bureau of Statistics there are 51.14% of people in Padang City who live in this zone [2].
According to the Meteorology Climatology and Geophysics Agency (BMKG), tsunamis in Indonesia can generally reach the coast about 10-60 minutes after the earthquake [1]. According to the Determining the path and place of tsunami evacuation is very important. Various efforts have been made by the government in general and BPDP coordinates with BMKG in particular to provide various information on the evacuation of tsunami warnings. One of them is to map out tsunami evacuation routes and widen the road and build tsunami evacuation shelters in high buildings.
The problem faced is the tsunami evacuation path that has been made by the government looks less effective and not enough to channel the mass so that the evacuation process is hampered. This resulted in a lot of very severe congestion in the streets of Padang for hours. Given the timing of a tsunami after a very short earthquake, such a situation would have caused many lives. Most of the people do not seem to consider vertical evacuation ie evacuation to buildings that have height and robustness so worthy of being shelter as an option in self-salvation. The evacuation takes place only as a horizontal movement away from the shore and leads to the mainland. Therefore, research on the determination of the shortest path of tsunami evacuation in Padang City is needed.
In determining the shortest path of tsunami evacuation in Padang City, it is assumed that in evacuating people walking or running so there is no traffic jam on the road. As we know the distance from the area along the coast of Padang to the tsunami safe zone is very far and impossible to travel by walking within 30 minutes, so in this study the evacuation is carried out vertically to the buildings that deserve to be shelter.
Determination of the shortest path can be searched with various algorithms, including Djiktra Algorithm, Bellmand-Ford Algorithm and Floyd-Warshall Algorithm. The Djiktra algorithm is a variant of the Greedy Algorithm, which is one of the most popular algorithms in problem solving related to optimization problems. The Djiktra algorithm can not calculate at once the shortest path for all pairs of vertices.
While Floyd-Warshall algorithm is one of the variants of dynamic programming, which is a method that solves the problem by looking at the solution that will be obtained as an interrelated decision. The solutions are formed from solutions that come from the previous stage and there is a possibility of more than one solution [7]. According Iftadi compared with other algorithms, Floyd-Warshall algorithm has several advantages, namely (1) determination of the shortest path can be determined from all pairs of vertices, (2) speed in determining the shortest path very quickly when applied in a system, (3) stable performance [3].
In this study the problem is limited to determining the shortest path of tsunami evacuation to Padang Utara Subdistrict. Where the initial vertex (point) is taken from some point on the shore of Padang Utara Subdistrict, the final node is taken from the shelter and the radius of two vertices taken has a distance of less than 400 meters.

Method
This research is an applied research that begins by analyzing theories relavan with problems, then continued with data retrieval. The data used are secondary data obtained from Regional Disaster Management Agency (BPBD) of Padang City and Public Works Department and Spatial Planning of Padang City, namely Evacuation Map of Padang City, Map of Padang Utara Subdistrict, name and length data of road segment. In reviewing the problems encountered, the steps taken are as follows: • Transforming the map of Padang Utara Subdistrict into a connected weights graph G(V,E). V is a set of vertex and E is a set of edge. • represents the graph G into an adjacent matrix form • then processed using Floyd-Warshall algorithm. The procedure is as follows: Step 1 : Represents the graph as a weighted matrix , where the weights for each side are The output is a matrix n x n, , where is a distance from node i to j. Based on , find , with .
Step 2 : set , input value Step 3 : If then . Otherwise Step 4 : If then and repeat step3, if then go to step 5 Step 5 : Step 6 : If then and go back to step 2, if then a.
is the shortest path weight from node i to node j b. is the shortest path passed from node i to node j c. The process is complete.

Description Data
To determine the shortest path of tsunami evacuation in Padang City using Floyd-Warshall Algorithm required data such as tsunami evacuation map of Padang City, name and length of road segment. Based on tsunami evacuation map of Padang City, it is seen that there are six sub-districts in Padang City including tsunami red zone. The six subdistricts can be seen in the table below.  Table 1, it can be seen that Padang Timur and Padang Utara sub-districts have high population density of 9,712 and 8,718 persons per km2. Therefore, in this study the authors limit the area of research in the District of Padang Utara. The population of Padang Utara is 70,444 people. With an area of only 8.08 km2, this indicates that the population here is relatively dense when compared to other sub-districts included in the red zone tsunami in Padang City. In solving the problem of determining the shortest path of tsunami evacuation in Padang City it is assumed that: • In evacuation the community is assumed to walk or run so that there is no traffic jam in the street. • The vertices on the graph are assumed with crossroads and shelters.
• The side of the graph is assumed with the road linking the intersection.
• The side weights are the distance or length of the road segment connecting the intersection.

Analysis Data
In this section that will be discussed is the shortest path problem solving for tsunami evacuation in Padang Utara District. The first step is to represent the map the area into a weighted graph. The formation of this graph refers to the assumptions outlined above. The graph formed consists of 97 vertices as shown in Figure 1. We use MATLAB R2014 to find the shortest path of tsunami evacuation with Floyd-Warshall Algorithm. Based on the graph in Figure 1, then the areas along the beach to be searched for the shortest path of evacuation to the nearest shelter are as follows: 1. Furthermore, the weighted graph is presented in the form of an adjacent matrix of 97 x 97. The resulting matrix is the initial matrix to be input into the Floyd-Warshall algorithm program. In addition, also entered the matrix of the point list, the matrix whose entries are lists of all points in the graph. From this matrix we can see trajectory that can be passed by the community during tsunami evacuation.
The matrix (the adjacent neighbor matrix) and the matrix (initial track matrix) are inputted to the Floyd-Warshall algorithm program with the help of MATLAB R2009a. After being processed using the Floyd-Warshall algorithm, two matrices are matrix and matrix . From the matrix , the shortest path of tsunami evacuation that can be passed by the community in Padang Utara District for all its vertices. While the matrix can be seen the shortest form of the tsunami evacuation trajectory that can be passed by the community in Padang Utara District.

Discussion
From the result of research using Floyd-Warshall Algorithm obtained the shortest path of evacuation of tsunami in District of Padang Utara. In addition, there is also a path that can be passed by people from the area along the coast to the vertical evacuation (shelter) as shown in Table 2. Based on Table 2, it can be determined the travel time of the shortest path of tsunami evacuation to the shelter by using the formula t = S / v, where S is the shortest distance from the evacuation area to the shelter (m), and v is the speed of the person walking at the time of evacuation (m / s ). According to [5]  From the above calculation obtained travel time for all evacuation areas along the coast of Padang Utara District less than 30 minutes. So that the tsunami evacuation path obtained by Floyd-Warshall Algorithm can be used as an evacuation route that can be passed by the community in Padang Utara Subdistrict.

Conclusion
Based on the above discussion it can be concluded that: 1. The shortest path for tsunami evacuation in Kecamatan Padang Utara can be formed by modeling the graph using the Floyd-Warshall Algorithm. The vertices on the graph represent crossroads and shelters, while the sides represent the road linking the two intersections. 2. The shortest path of tsunami evacuation that can be passed by the community from several to coastal areas in Padang Utara Subdistrict is as follows: 3. For Patenggangan and Pantai Gajah Barat area is to the FIP UNP shelter with the shortest distance of 1055 meters and 950 meters respectively. 4. For the area of Pantai Gajah VI is to shelter Pustaka UNP with the shortest distance of 360 meters. 5. For Elephant Coast IX area, Gang Belibis D2, Parkit Beach VI and Parkit Ujung Beach are to FIK UNP shelters with the shortest distance of 690 meters, 415 meters, 550 meters and 800 meters respectively. 6. For Kali Tepi area, UBH Beach, Jl. Mother V and Gang Bahari 2 is to UBH Campus shelter with the shortest distance of 250 meters, 165 meters, 480 meters and 800 meters respectively. 7. For the area of Jl. Bahari 2 and Jl. The seafront is to the SDN 15 Lolong shelter with the shortest distance of 235 meters and 80 meters respectively.