bild
Skolan för
elektroteknik
och datavetenskap

Uppgift 8 våren 2010

Uppgiften ska lämnas till din övningsledare på övningen den 1/4. För godkänt måste du ha gjort samtliga deluppgifter. Det är tillåtet att göra enstaka fel och misstag men det är viktigt att du försöker lösa samtliga uppgifter. Om du kör fast med någon uppgift så finns det som vanligt hjälp att få på labbarna.

Hemuppgift

Läs om filer och felhantering i kapitel 12 i programmeringsboken. Studera programmet Grep.java. Det är en förenklad version (som inte hanterar reguljära uttryck) av Unixkommandot grep. Vid behov, friska upp dina kunskaper om strömmar, stdin, stdout, stderr i Unix. Du får själv hitta lämpliga källor.

Skriftlig uppgift

Din uppgift är att skriva ett program som anropas på följande sätt i Unix.

java Path FROM TO
FROM och TO är två heltal som anger en startnod och en slutnod i en graf. Programmet ska skriva ut noderna på någon väg från FROM till TO om det finns en sådan väg i grafen, annars skriver programmet ut en tom rad. Vägen ska innehålla minimalt antal noder. Använd breddenförstsökning.

Grafen finns lagrad i en fil med namnet Distances.txt. Noderna är numrerade 0, 1, 2, ..., n-1. Filens första rad innehåller talet n. De andra raderna innehåller tre tal i, j och d separerade med blanktecken. Det positiva talet d anger avståndet mellan noderna i och j. Filen kan också innehålla "//"-kommentarer och tomma rader. Kommentarerna fungerar på samma sätt som i Java. Här är ett exempel på en fil som beskriver en liten graf.

// This is a database with distances between a number
// of cities. The cities are numbered 0, 1, 2, ..., n-1.
// The first lines contains the integer n, i.e. the
// number of cities. Each following line contains three
// integers i, j, and d separated by spaces. The positive
// number d is the distance between i and j.

6        // Size

0 1 100  // First edge
0 3 80
0 5 25
1 2 120
1 5 60
2 3 50
3 4 100
4 5 200  // Last edge

Vid eventuella fel så ska programmet skriva ut ett relevant felmeddelande till stderr och inte skriva något på stdout.

Valfri extrauppgift

Kraven är desamma som i den obligatoriska uppgiften men du skall i stället skriva ut den kortaste vägen mellan start- och slutnod. Använd Dijkstras algoritm.

Copyright © Sidansvarig: Stefan Nilsson <snilsson@nada.kth.se>
Uppdaterad 2010-02-24