AI: The cheapest route

Use uniform-cost search to find the lowest-cost route on a road map.

What to build

A program that finds the cheapest route between two towns.

Requirements

  • Roads go both ways and have positive costs. If several routes have the same lowest cost, print the one that comes first when the routes are compared town by town in alphabetical order.
  • Print the route as A -> B -> C and then cost N, or print no route.

Input

Line 1: r. Then r lines TOWN TOWN COST. Last line: the start and the goal.

Output

Two lines, or no route.

Constraints

r ≤ 200; town names have no spaces.

Example

Input:

5
A B 4
A C 1
C B 2
B D 5
C D 8
A D

Output:

A -> C -> B -> D
cost 8

Why it works

Uniform-cost search takes routes out of the frontier in order of cost, so the goal comes out first along a cheapest route.

Examples

Example 1 · Input
5
A B 4
A C 1
C B 2
B D 5
C D 8
A D
Expected output
A -> C -> B -> D
cost 8
Example 2 · Input
2
A B 1
C D 1
A D
Expected output
no route

Prompts inside input() are ignored when checking, so input("n: ") is fine.

Hints

Hint 1

Use a priority queue of (cost, path); the first time the goal is taken out, its path is the cheapest.

Hint 2

Storing the whole path as a list makes ties come out in alphabetical order automatically.

Solution

Show one correct solution (try it yourself first)
import heapq

roads = {}
for _ in range(int(input())):
    a, b, cost = input().split()
    roads.setdefault(a, {})[b] = int(cost)
    roads.setdefault(b, {})[a] = int(cost)
start, goal = input().split()
frontier, done, answer = [(0, [start])], set(), None
while frontier:
    cost, path = heapq.heappop(frontier)
    town = path[-1]
    if town in done:
        continue
    done.add(town)
    if town == goal:
        answer = (cost, path)
        break
    for nxt, step in roads.get(town, {}).items():
        if nxt not in done:
            heapq.heappush(frontier, (cost + step, path + [nxt]))
if answer:
    print(" -> ".join(answer[1]))
    print("cost", answer[0])
else:
    print("no route")

Lesson: Problem solving by search →