Ein häufiges Alltagsproblem ist es, in einem Verkehrsnetz die schnellste Verbindung zwischen zwei Punkten zu finden. Bei mittlerer Komplexität des Netzes und einer graphischen Übersicht lösen die meisten Menschen diese Aufgabe ohne Schwierigkeiten; für den Computer ist die Sache schon deutlich komplizierter.
In dieser Aufgabe betrachten wir einen vereinfachten Ausschnitt des Londoner U-Bahn-Netzes mit 50 Bahnhöfen und sieben Linien:
Oder der gleiche Ausschnitt in Farbe.
Die Linien und ihre Bahnhöfe sind in der nachfolgenden Liste enthalten, wobei Umsteigebahnhöfe durch einen Stern hinter dem Namen gekennzeichnet sind. Wer die Liste nicht abtippen möchte, aber Zugang zum Netz hat, kann sie sich hier herunterladen.
Zur Bestimmung der schnellsten Verbindung legen wir die folgenden vereinfachenden Annahmen zugrunde:
Schreiben Sie ein Programm, welches nach Eingabe der festen Umsteigezeit und zweier Bahnhöfe aus der Liste eine genaue Beschreibung der schnellsten Verbindung (Namen der Linien und passierte Bahnhöfe) ausgibt. Wenn es mehrere gleich schnelle Verbindungen gibt, sollen diese alle ausgegeben werden. Senden Sie mehrere Beispielausgaben ein, darunter auch je eine für die drei Verbindungen Gloucester Road nach King's Cross, Leicester Square nach Baker Street und Paddington nach Bond Street; legen Sie dabei eine Umsteigezeit von drei Minuten zugrunde.
BAKERLOO: Embankment* Charing Cross* Piccadilly Circus* Oxford Circus* Regent's Park Baker Street* Marylebone Paddington* CENTRAL: Notting Hill Gate* Queensway Lancaster Gate Marble Arch Bond Street* Oxford Circus* Tottenham Court Road* Holborn* Chancery Lane St. Paul's Bank/Monument* Liverpool Street* CIRCLE: Notting Hill Gate* Bayswater Paddington* Edgeware Road Baker Street* Great Portland Street Euston Square King's Cross/St. Pancras* Farringdon Barbican Moorgate Liverpool Street* Aldgate Tower Hill Bank/Monument* Cannon Street Mansion House Blackfriars Temple Embankment* Westminster St. James's Park Victoria* Sloane Square South Kensington* Gloucester Road* High Street Kensington Notting Hill Gate*
JUBILEE: Charing Cross* Green Park* Bond Street* Baker Street* NORTHERN: Embankment* Charing Cross* Leicester Square* Tottenham Court Road* Goodge Street Warren Street* Euston* PICCADILLY: Earl's Court Gloucester Road* South Kensington* Knightsbridge Hyde Park Corner Green Park* Piccadilly Circus* Leicester Square* Covent Garden Holborn* Russel Square King's Cross/St. Pancras* VICTORIA: Victoria* Green Park* Oxford Circus* Warren Street* Euston* King's Cross/St. Pancras*