Jakarta Railway Route Shortest Path with Dijkstra Algorithm

Overview

Have you ever heard the statement "Leetcode is Overrated" or "You probably won't ever use all those complex algorithms and data structures that you learn in those boring lectures"?

My previous experience proves that knowing at least some basic data structure will help your career quite a lot. In this article, I'll elaborate on it!

The App Goal

The app's name is Comute, a navigation app that mainly focuses on helping deaf people commute by Train in Jakarta, Indonesia area. The app's main function is to:

1. Track user location
2. Generate shortest path route containing the list of stations the user needs to pass
3. Notify them on certain stations (usually transit and end station)

To achieve the station route, most of the time people will look into an API such as Google Maps API or OpenStreetMap. The main problem with them is that:

• It requires network
• Probably not free and not cheap either

Hence, I found a workaround which is to calculate the shortest path ourselves using Dijkstra algorithm.

Dijkstra Algorithm

Purpose and Use Cases

With Dijkstra's Algorithm, you can find the shortest path between nodes in a graph. Particularly, you can find the shortest path from a node (called the "source node") to all other nodes in the graph, producing a shortest-path tree.

This algorithm is used in GPS devices to find the shortest path between the current location and the destination. It has broad applications in industry, especially in domains that require modeling networks.

History

This algorithm was created and published by Dr. Edsger W. Dijkstra, a brilliant Dutch computer scientist and software engineer. In 1959, he published a 3-page article titled "A note on two problems in connexion with graphs" where he explained his new algorithm.

During an interview in 2001, Dr. Dijkstra revealed:

"What's the shortest way to travel from Rotterdam to Groningen? It is the algorithm for the shortest path, which I designed in about 20 minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path."

Basic Concept

Graphs are data structures used to represent "connections" between pairs of elements:

• Nodes represent real-life objects, persons, or entities
• Edges are the connections between nodes

Two nodes are connected if there is an edge between them.

Algorithm Steps

In a summarized way, the algorithm:

1. Take a boolean array spt[] and initialize all elements to 0 (0 = unvisited, 1 = visited)
2. Create an array v[] which holds the distance of nodes from starting node and initialize it to infinity
3. Start at the node given as a parameter and return the shortest path between this node and all other nodes
4. Calculate the shortest distance from each node to the source and save this value if it finds a shorter path
5. Once the shortest path is found, mark the node as visited
6. Repeat steps 4 and 5 until all nodes are visited

Time Complexity

Dijkstra's Algorithm complexity can vary depending on implementation, but normally it is O(n²) where n is the number of vertices. The space complexity is O(n).

Implementation for Jakarta Railway

For the Comute app, we modeled the Jakarta railway system as a graph where:

• Each station is a node
• Connections between stations are edges
• Edge weights represent travel time between stations

struct Station {
    let name: String
    let connections: [(station: Station, travelTime: Int)]
}

func dijkstra(start: Station, end: Station) -> [Station] {
    var distances: [String: Int] = [:]
    var previous: [String: Station?] = [:]
    var unvisited: Set<String> = []
    
    // Initialize distances
    for station in allStations {
        distances[station.name] = Int.max
        previous[station.name] = nil
        unvisited.insert(station.name)
    }
    distances[start.name] = 0
    
    while !unvisited.isEmpty {
        // Find minimum distance node
        let current = unvisited.min { distances[$0]! < distances[$1]! }!
        unvisited.remove(current)
        
        if current == end.name { break }
        
        // Update neighbors
        for (neighbor, time) in currentStation.connections {
            let alt = distances[current]! + time
            if alt < distances[neighbor.name]! {
                distances[neighbor.name] = alt
                previous[neighbor.name] = currentStation
            }
        }
    }
    
    return reconstructPath(previous, end)
}

Results

The Comute app was:

• Featured by Apple Developer Academy
• Highlighted in Detik.com (a major Indonesian news outlet)
• Achieved over 1,800 user downloads

Conclusion

This experience taught me that data structures and algorithms are not just academic exercises. They have real-world applications that can help people in their daily lives. The Dijkstra algorithm, designed in 20 minutes over coffee, continues to power navigation systems worldwide.