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
- Begin with 10–15 Istanbul stations rather than importing the entire network.
- Use travel minutes as weights and document that the figures are illustrative.
- Add explicit transfer edges with a separate interchange penalty.
- Keep fare, accessibility and crowding as separate attributes before combining them.
- Display predecessor links so the selected route can be reconstructed visibly.
- Test routes that cross major interchanges and routes with no available connection.
- Validate any Australian or Istanbul transport data before presenting it as current.
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.