Using the Istanbul metro map to demonstrate Dijkstra’s algorithm

A metro map is an accessible way to understand Dijkstra’s algorithm because it turns an abstract graph into a familiar journey. Stations become vertices, rail connections become edges, and the time or distance between stops becomes a weight. Istanbul is especially useful because its network combines metro lines, trams, funiculars, Marmaray services and ferry connections across two continents.

The method also suits Australian learners who already think in terms of transport networks, whether they use Sydney’s Opal system, Melbourne’s myki, Brisbane’s go card, Perth’s SmartRider or Adelaide’s MetroCARD. By treating transfers and travel time as measurable costs, a route-planning exercise can show why the fastest path is not always the one with the fewest stations.

Turning the Istanbul map into a graph

Start with a simplified section of the Istanbul rail network. Stations such as Yenikapı, Vezneciler-İstanbul Üniversitesi, Şişhane, Taksim, Levent, Hacıosman, Üsküdar, Ayrılık Çeşmesi and Kadıköy can be represented as nodes. Each direct service between neighbouring stations becomes an edge joining two nodes.

The edge weight should reflect the problem being solved. If the goal is the shortest physical journey, use kilometres. For a commuter-facing application, minutes are usually more useful. A connection might be assigned four minutes between stations, while a transfer at a busy interchange could add six or ten minutes. This makes the model closer to real travel, where changing platforms matters.

A useful dataset might store each connection in both directions:

Yenikapı -> Vezneciler: 3 minutes
Yenikapı -> Üsküdar: 5 minutes
Taksim -> Şişhane: 2 minutes
Şişhane -> Hacıosman: 24 minutes
Üsküdar -> Ayrılık Çeşmesi: 4 minutes

The figures are illustrative rather than an official timetable. A production journey planner would need validated operating data, station accessibility information, service disruptions and timetable changes.

How Dijkstra searches for the best route

Dijkstra’s algorithm begins by assigning a tentative distance of zero to the starting station and infinity to every other station. It then selects the unvisited station with the smallest known distance. From that station, it checks each connected neighbour and asks whether travelling through the current station produces a shorter route.

Suppose the journey starts at Kadıköy. The algorithm may first examine Ayrılık Çeşmesi, then Üsküdar or a central interchange, depending on the graph and the chosen weights. When it discovers a shorter path to a station, it updates that station’s distance and records the previous node. This predecessor record allows the final route to be reconstructed after the destination is reached.

The key rule is that a station removed from the priority queue with the smallest distance is settled when all weights are non-negative. That condition is satisfied by travel times, distances and transfer penalties. A binary-heap priority queue gives the familiar time complexity of O((V + E) log V), where V is the number of stations and E is the number of connections.

This step-by-step logic is similar to the discipline behind a face recognition module: a complex process becomes manageable when its inputs, decisions and measurable outputs are represented clearly. In a classroom or software project, logging each relaxation makes the route choice easy to inspect.

Comparing route weights and practical priorities

The same Istanbul map can produce different answers when the weighting system changes. A route with fewer stops may involve a long interchange, while a route with more stops could be faster because it avoids a crowded transfer. This is why a map alone cannot define “best”; the application must decide what best means.

Routing objective Edge weight Likely result Useful context
Fewest stops One per station Minimum station count Simple map exercises
Fastest trip Minutes between stops Lowest estimated travel time Daily commuting
Lowest transfer burden Time plus interchange penalty Fewer changes Luggage or mobility needs
Shortest physical route Track distance Minimum kilometres Network analysis
Accessible journey Time plus lift and platform constraints Step-free option Wheelchair or pram travel

For Australian comparisons, the transfer penalty is easy to understand. A passenger changing trains at Central in Sydney may value a slightly longer route if it avoids a difficult platform connection. In Melbourne, a journey involving a tram interchange may require different assumptions from a fully separated metro trip. Brisbane’s network can likewise be modelled with walking links between rail and busway stations.

Fare is another possible weight, although it should usually be kept separate from travel time. Istanbul’s integrated transport environment includes different modes and transfer rules, while Australian systems use their own card and fare structures. Adding cost to the same weight can produce confusing results unless the units are normalised. A multi-objective planner might instead calculate time, price and accessibility as separate scores.

Building a small working implementation

A compact implementation can use an adjacency list, where each station maps to a collection of neighbouring stations and weights. This is more efficient than a full matrix for a sparse metro network. The algorithm needs three main structures: a distance dictionary, a predecessor dictionary and a min-priority queue.

Pseudocode looks like this:

distance[start] = 0
push (0, start) into priority queue

while queue is not empty:
    current_distance, station = pop smallest
    if current_distance is greater than distance[station]:
        continue

    for neighbour, weight in graph[station]:
        candidate = current_distance + weight
        if candidate < distance[neighbour]:
            distance[neighbour] = candidate
            previous[neighbour] = station
            push (candidate, neighbour)

After the destination is settled, follow previous backwards from the destination to the origin, then reverse the resulting list. If the destination is unreachable, the program should return a clear status rather than an empty route. Real applications should also handle closed stations, cancelled services and temporary track changes.

For a learner in Australia, a practical exercise is to compare the Istanbul model with a familiar local corridor, such as Sydney Metro between Chatswood and Martin Place or a Melbourne trip involving a tram. Use public network maps for the topology, but avoid presenting estimated weights as live travel advice. Network data ages quickly, especially during construction or timetable revisions.

Visualising results for commuters and students

A strong demonstration highlights the algorithm’s decisions rather than displaying only the final path. Colour the settled stations, show tentative distances beside each node and animate the priority queue’s next selection. When the route changes because a transfer penalty is added, viewers can see how the objective shapes the answer.

The interface can also show multiple routes: fastest, fewest transfers and shortest distance. This is valuable in Istanbul, where crossing between the European and Asian sides may involve rail, ferry or interchange choices. It mirrors Australian commuter preferences, such as choosing a cooler, less crowded route during a hot Perth afternoon or avoiding stairs while travelling with a pram in Sydney.

A map-based project should distinguish geographic accuracy from algorithmic clarity. A stylised diagram is often better for teaching because it keeps labels readable and makes edge weights visible. Once the algorithm works, geographic coordinates, line colours, station icons and real-time disruption layers can be added without changing the core search logic.

Recommendations for a reliable demonstration

A finished demonstration should make three ideas unmistakable: a metro map is a weighted graph, Dijkstra repeatedly chooses the cheapest unsettled option, and the definition of “cheapest” depends on the chosen weights. The concrete next step is to create a small adjacency list for Yenikapı, Üsküdar, Ayrılık Çeşmesi, Kadıköy, Taksim, Şişhane and Hacıosman, then run the algorithm from Kadıköy to Hacıosman with transfer penalties included.