A city route planner

The problem

Build a program that reads a map of cities and roads, and finds the route with the fewest roads between any two cities.

Requirements

• City names are turned into vertex numbers with a hash table
• The roads are stored in adjacency lists
• A breadth-first search finds the fewest roads between two cities, and the route itself is printed
• Two cities with no route between them give a clear message
• A command reports how many separate regions the map has
• All memory is freed when the program ends

Technologies

• C
• Hash tables
• Graphs
• Queues
• Breadth-first search

Step by step

1. Write the hash table that maps a city name to its number, adding the name when it is new.
2. Read the roads and build the adjacency lists, adding each road in both directions.
3. Write breadth-first search with a queue, recording for each city the city it was reached from.
4. Print a route by following those records back from the destination, and reversing them with a stack.
5. Count the regions by starting a new search from every city that has not been visited.
6. Test with a single city, with two unconnected regions, and with a map that has a loop.

Expected result

A working route planner that answers shortest-route questions on a map of named cities.

How it is evaluated

• Every route is correct, and no shorter route exists
• Unknown cities and unreachable cities are handled calmly
• The hash table handles collisions
• No memory is leaked

Ways to improve it

• Give each road a length, and find the shortest distance with a priority queue
• Suggest city names from their first letters with a trie
• Add one-way roads